原題鏈接：
https://leetcode-cn.com/problems/move-zeroes/

給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。

示例:

輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:

必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。
盡量減少操作次數(shù)。

算法

/**
簡單粗暴的一種解題方法，類似于冒泡排序
兩次遍歷。每次遍歷前后元素比較，前一個為0，后一個不為0則交換，遍歷完成之后，會有一個為0的元素到數(shù)組的最后一個位置，然后進行下一次遍歷，直到所有元素遍歷完成。所有為0的元素都放在數(shù)組最后。
 時間復(fù)雜度 O(n^2)
 空間復(fù)雜度 O(1)
 提交LeetCode時不通過，因為數(shù)據(jù)量太大時耗時太多
*/
func moveZeroes(_ nums: inout [Int]) {
    for i in 0..<nums.count {
        for j in stride(from: i+1, to: nums.count, by: 1) {
            if nums[i] == 0 && nums[j] != 0 {
                let temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
            }
        }
    }
}
/**
 輸入：[0,1,0,3,12]
 每次交換的結(jié)果：
 [1, 0, 0, 3, 12]
 [1, 0, 0, 3, 12]
 [1, 0, 0, 3, 12]
 [1, 0, 0, 3, 12]
 [1, 0, 0, 3, 12]
 [1, 3, 0, 0, 12]
 [1, 3, 0, 0, 12]
 [1, 3, 0, 0, 12]
 [1, 3, 12, 0, 0]
 [1, 3, 12, 0, 0]
 */

/**
 時間復(fù)雜度O(n)
 空間復(fù)雜度O(1)
 快慢指針
 i : 快指針
 lastNonZeroIndex : 慢指針（最后一個非零指針）
 第一次遍歷，向前移動所有的非零數(shù)字，慢指針之前都是非零，之后都是零
 第二次遍歷，慢指針之后的數(shù)字賦值為零
 */
func moveZeroes(_ nums: inout [Int]) {
    var lastNonZeroIndex = 0
    for i in 0..<nums.count {
        if nums[i] != 0 {
            // 向前移動非零數(shù)字
            nums[lastNonZeroIndex] = nums[i]
            // 最后非零指針向后移動一位
            lastNonZeroIndex = lastNonZeroIndex + 1
        }
    }
    // 以上遍歷完成之后，lastNonZeroIndex之前的數(shù)字都是非零，之后的數(shù)字都是0
    // 再次遍歷，將lastNonZeroIndex之后的元素全部賦值為0
    for i in lastNonZeroIndex..<nums.count {
        nums[i] = 0
    }
}

??動畫演示

/**
 時間復(fù)雜度O(n)
 空間復(fù)雜度O(1)
 快慢指針
 進一步優(yōu)化
 類似快速排序，將0作為中間的數(shù)字進行左右分割，等于0的元素放在右邊，不等于0的元素放在左邊。
 */
func moveZeroes(_ nums: inout [Int]) {
    var lastNonZeroIndex = 0
    for i in 0..<nums.count {
        if nums[i] != 0 {
            // 直接進行交換
            let temp = nums[lastNonZeroIndex]
            nums[lastNonZeroIndex] = nums[i]
            nums[i] = temp
            // 交換也可以這么寫
            //    (nums[i], nums[lastNonZeroIndex]) = (nums[lastNonZeroIndex], nums[i])

            lastNonZeroIndex = lastNonZeroIndex + 1
        }
    }
}

??動畫演示

/**
 時間復(fù)雜度O(n)
 空間復(fù)雜度O(1)
 快慢指針
 參考了國際站的題解之后在上一個基礎(chǔ)上再次優(yōu)化
 */
func moveZeroes(_ nums: inout [Int]) {
    // 過濾掉不需要處理的情況
    // 數(shù)組元素小于2個，直接返回
    guard nums.count > 1 else {
        return
    }
    var lastNonZeroIndex = 0
    for i in 0..<nums.count {
        if nums[i] != 0 {
            if i > lastNonZeroIndex {
                // 通過以上 i > lastNonZeroIndex 避免了兩個 i == lastNonZeroIndex 時的冗余操作
                // 交換 改為 賦值，非零數(shù)字賦值到零數(shù)字的位置，之前非零的位置可以直接賦值為零（交換也是賦值為零，所以直接進行賦值零）
                nums[lastNonZeroIndex] = nums[i]
                nums[i] = 0
            }
            // 非零就后移一位
            lastNonZeroIndex += 1
        }
    }
}

var nums = [0,1,0,3,12]
moveZeroes(&nums)

以上算法的一步步優(yōu)化參考了中文站和國際站上的一些題解。
LeetCode上有一位同學(xué)的題解非常好，比官方的題解更容易理解。鏈接：https://leetcode-cn.com/problems/move-zeroes/solution/dong-hua-yan-shi-283yi-dong-ling-by-wang_ni_ma/
以上的動畫演示都是出自這位同學(xué)的題解，如有侵權(quán)，請聯(lián)系刪除。

GitHub：https://github.com/huxq-coder/LeetCode
歡迎star