携手创作，共同成长！这是我参与「日新方案 8 月更文应战」的第30天，点击查看活动详情

标题

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

请注意，必须在不仿制数组的情况下原地对数组进行操作。

示例 1：

  • 输入： nums = [0,1,0,3,12]
  • 输出： [1,3,12,0,0]

示例 2：

  • 输入： nums = [0]
  • 输出： [0]

办法一：双指针

思路及解法

运用双指针，左指针指向当时现已处理好的序列的尾部，右指针指向待处理序列的头部。

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交流，一起左指针右移。

注意到以下性质：

  1. 左指针左面均为非零数；

  2. 右指针左面直到左指针处均为零。

因此每次交流，都是将左指针的零与右指针的非零数交流，且非零数的相对次序并未改动。

代码

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        let n: Int = nums.count
        var left: Int = 0
        var right: Int = 0
        while right < n {
            if 0 != nums[right] {
                nums.swapAt(left, right)
                left += 1
            }
            right += 1
        }
    }
}

复杂度剖析

  • 时刻复杂度：O(n)O(n)，其间 nn 为序列长度。每个方位至多被遍历两次。

  • 空间复杂度：O(1)O(1)。只需要常数的空间存放若干变量。

办法二：两次遍历

思路及解法

咱们创建两个指针 i 和 j，第一次遍历的时分指针j用来记载当时有多少非 0 元素。即遍历的时分每遇到一个非 0 元素就将其往数组左面挪，第一次遍历完后，j 指针的下标就指向了最后一个非 0 元素下标。

第2次遍历的时分，起始方位就从 j 开始到完毕，将剩余的这段区域内的元素全部置为 0。

代码

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        let n: Int = nums.count
        var j = 0
        for i in 0..<n {
            if 0 != nums[i] {
                nums[j] = nums[i]
                j += 1
            }
        }
        for i in j..<n {
            nums[i] = 0
        }
    }
}

复杂度剖析

  • 时刻复杂度：O(n)O(n)，其间 nn 为序列长度。

  • 空间复杂度：O(1)O(1)。

办法三：一次遍历

思路及解法

这儿参考了快速排序的思想，快速排序首先要确认一个待分割的元素做中心点 x，然后把所有小于等于 x 的元素放到 x 的左面，大于 x 的元素放到其右边。

这儿咱们可以用 0 当做这个中心点，把不等于 0（注意标题没说不能有负数）的放到中心点的左面，等于 0 的放到其右边。

这的中心点便是 0 本身，所以完成起来比快速排序简略很多，咱们运用两个指针 i 和 j，只要 0 != nums[i]，咱们就交流 nums[i] 和 nums[j]。

代码

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        let n: Int = nums.count
        var j = 0
        for i in 0..<n {
            if 0 != nums[i] {
                let temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                j += 1
            }
        }
    }
}

复杂度剖析

  • 时刻复杂度：O(n)O(n)，其间 nn 为序列长度。

  • 空间复杂度：O(1)O(1)。