LeetCode - 283. 移动零 swift

原题链接：
https://leetcode-cn.com/problems/move-zeroes/

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

算法

/**
简单粗暴的一种解题方法，类似于冒泡排序
两次遍历。每次遍历前后元素比较，前一个为0，后一个不为0则交换，遍历完成之后，会有一个为0的元素到数组的最后一个位置，然后进行下一次遍历，直到所有元素遍历完成。所有为0的元素都放在数组最后。
 时间复杂度 O(n^2)
 空间复杂度 O(1)
 提交LeetCode时不通过，因为数据量太大时耗时太多
*/
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]
 每次交换的结果：
 [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]
 */

/**
 时间复杂度O(n)
 空间复杂度O(1)
 快慢指针
 i : 快指针
 lastNonZeroIndex : 慢指针（最后一个非零指针）
 第一次遍历，向前移动所有的非零数字，慢指针之前都是非零，之后都是零
 第二次遍历，慢指针之后的数字赋值为零
 */
func moveZeroes(_ nums: inout [Int]) {
    var lastNonZeroIndex = 0
    for i in 0..<nums.count {
        if nums[i] != 0 {
            // 向前移动非零数字
            nums[lastNonZeroIndex] = nums[i]
            // 最后非零指针向后移动一位
            lastNonZeroIndex = lastNonZeroIndex + 1
        }
    }
    // 以上遍历完成之后，lastNonZeroIndex之前的数字都是非零，之后的数字都是0
    // 再次遍历，将lastNonZeroIndex之后的元素全部赋值为0
    for i in lastNonZeroIndex..<nums.count {
        nums[i] = 0
    }
}

👆动画演示

/**
 时间复杂度O(n)
 空间复杂度O(1)
 快慢指针
 进一步优化
 类似快速排序，将0作为中间的数字进行左右分割，等于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
        }
    }
}

👆动画演示

/**
 时间复杂度O(n)
 空间复杂度O(1)
 快慢指针
 参考了国际站的题解之后在上一个基础上再次优化
 */
func moveZeroes(_ nums: inout [Int]) {
    // 过滤掉不需要处理的情况
    // 数组元素小于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 时的冗余操作
                // 交换 改为 赋值，非零数字赋值到零数字的位置，之前非零的位置可以直接赋值为零（交换也是赋值为零，所以直接进行赋值零）
                nums[lastNonZeroIndex] = nums[i]
                nums[i] = 0
            }
            // 非零就后移一位
            lastNonZeroIndex += 1
        }
    }
}

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

以上算法的一步步优化参考了中文站和国际站上的一些题解。
LeetCode上有一位同学的题解非常好，比官方的题解更容易理解。链接：https://leetcode-cn.com/problems/move-zeroes/solution/dong-hua-yan-shi-283yi-dong-ling-by-wang_ni_ma/
以上的动画演示都是出自这位同学的题解，如有侵权，请联系删除。

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