移动零

移动零

Scroll Down

移动零

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

示例:

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

说明:

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

1、双指针

class Solution {
    public void moveZeroes(int[] nums) {
        //...省略判空
        for (int p = 0, i = 0; i < nums.length; i++) {
                    if (nums[i] != 0) {
                        int temp = nums[i];
                        nums[i] = nums[p];
                        nums[p++] = temp;
                    }
                }
    }
}

不考虑数组为空或者长度为0为1的情况,多加一个if而已。

开始时两个指针都指向第1个元素,然后判断当前值是否为0,如果是0,则 p 指针维持原位置不动,i 指针向后移动一位,当 i 指针指向的元素不为0的时候,

则将其与p指针的下一个元素交换(此时 p 指针的下一个元素一定是0),同时 p 指针向后移动一位。

重复此过程直至到最后一位,

2、标记后统一清零

class Solution {
    public void moveZeroes(int[] nums) {
        //...省略判空
      int index = 0;
      for(int num:nums){
          if(num!=0){
              nums[index++]=num;
          }
      }
      while(index<nums.length){
          nums[index++] = 0;
      }
    }
}

这个方法相当于把当前数组整个重新构造了一遍。

可以看作是从前往后数,有一个分界线,此分界之前全不为0,分界之后全为0。

遍历数组,只要当前数不为零,就将此值依次放到分界线之前的位置上。

放完之后,不管后面还剩几个位置,全部置为0即可。