题目

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

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

示例 1:

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

示例 2:

1
2
输入: nums = [0]
输出: [0]

提示:

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

实现代码

双指针实现，定义p1、p2，都指向第一个元素，如果p1值为0，则p2向前移动找出不为0的值和p1进行交换，直到p2 = nums.length；

p2的作用就是为p1找出不为0的值进行替换;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public void moveZeroes(int[] nums) {
    int p1 = 0, p2 = 0;
    while (p2 < nums.length) {
      if (nums[p1] == 0) {
        if (nums[p2] == 0) {
          p2++;
          continue;
        }
        nums[p1] = nums[p2];
        // 不替换了，直接赋值0
        nums[p2] = 0;
      }else{
        p2++;
      }
      p1++;
    }
  }
}

时间复杂度

只有数组O(n)

空间复杂度

额外空间p1、p2，常数级别O(1)