LeetCode-283.移动零

发表于 分类于

题目描述

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

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

示例

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
1
2
输入: nums = [0]
输出: [0]

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

题解

方法1

思路：

  1. 使用双指针，左指针左边表示已处理好的序列，右指针指向待处理序列的头部。
  2. 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
1
2
3
4
5
6
7
8
9
10
11
func moveZeroes(_ nums: inout [Int]) {
  var i = 0
  var j = 0
  while j < nums.count {
    if nums[j] != 0 {
      nums.swapAt(i, j)
      i += 1
  	}
  	j += 1
  }
}

方法二

思路：

  1. 左指针左边表示已经处理好的序列，右指针指向待处理序列的头部；
  2. 右指针不断后移，当右指针指向非零的元素，将当前元素放到左指针的位置，同时左指针右移一位。右指针继续后移；
  3. 当右指针达到元素结尾，查找结束，左指针及它后面的元素都赋值为0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func moveZeroes2(_ nums: inout [Int]) {
  var left = 0
  var right = 0

  while (right < nums.count) {
    if (nums[right] != 0) {
        nums[left] = nums[right]
        left += 1
    }
    right += 1
  }
  while (left < nums.count) {
    nums[left] = 0
    left += 1
  }
}