移动零

发表于 分类于 阅读次数：

移动零（难度：简答）

1580888243775

问题的两个要求是：

  • 将所有 0 移动到数组末尾。
  • 所有非零元素必须保持其原始顺序。

这里很好地认识到这两个需求是相互排斥的，也就是说，你可以解决单独的子问题，然后将它们组合在一起以得到最终的解决方案。

方法：

  • 一个指针i从前到后遍历数组，每当遇到非0数时，令 nums[cur] = nums[i]; cur++;，cur是另一个指针（从0开始），记录当前位置。
  • 当i遍历完后，此时cur指向的位置到数组的末尾全赋为0即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void moveZeroes(int[] nums) {
        int cur = 0;

        for(int i = 0; i < nums.length; i++){
            if(nums[i]!=0){
                nums[cur] = nums[i];
                cur++;
            }
        }

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

    }
}
1580890229187

复杂度

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