moveZeroes

283. 移动零

算法

i 用于记录非零元素的位置
遍历数组时，将非零元素按顺序填入数组前部，并记录当前插入的位置
遍历完成后，数组前部已填满非零元素，后续位置全部填充 0

复杂度分析

时间复杂度

遍历数组一次，时间复杂度为 O(n)
填充零的操作也是 O(n) ，但两者不重叠，总体为O(n)

空间复杂度

使用了两个指针变量，空间复杂度为 O(1)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    void moveZeroes(vector<int>& nums)
    {
        int i = 0; // 指针 i，用于记录下一个非零元素的位置

        // 1. 遍历数组，将所有非零元素依次放到前部
        for (int num : nums)
        {
            if (num != 0)
            {
                nums[i++] = num; // 将非零元素放入 i 位置，并移动 i
            }
        }

        // 2. 将剩余位置填充为 0
        while (i < nums.size())
        {
            nums[i++] = 0;
        }
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
  def moveZeroes(self, nums: List[int]) -> None:
    i = 0
    for x in nums:
      if x != 0:
        nums[i] = x
        i += 1

    while i < len(nums):
      nums[i] = 0
      i += 1

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func moveZeroes(nums []int)  {
  i := 0

  for _, x := range nums {
    if x != 0 {
      nums[i] = x
      i ++
    }
  }

  for i < len(nums) {
    nums[i] = 0
    i ++
  }
}

JavaScript 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let i = 0;

  for (let x of nums) {
    if (x != 0) {
      nums[i++] = x;
    }
  }

  while (i < nums.length) {
    nums[i++] = 0;
  }
};