283. 移动零 [简单]

数组双指针

题目链接：

https://leetcode.cn/problems/move-zeroes/
限制：必须在不复制数组的情况下原地对数组进行操作

方案一：

解题思路：

• 先抛开额外限制，把功能实现了再说
• 新建一个数组newNums用来记录非零数据

• 在一个新的循环中将 newNums 中的数据复制回 nums 中

  解题代码：

  class Solution {
    public void moveZeroes(int[] nums) {
        int[] newNums = new int[nums.length];
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count++;
            } else {
                newNums[i - count] = nums[i];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = newNums[i];
        }
    }
  }

  运行结果：

  

  复杂度分析：

• 时间复杂度：O(n)，出现了两个平级的 for 循环

• 空间复杂度：O(n)，创建了额外的 newNums 数组

  方案二：

  解题思路：

• 考虑题目中的额外限制，在方案一的基础上尝试优化

• 剔除 newNums 数组后，改写如下代码的第 8 行

• 再来解决数组尾部赋值为 0 的逻辑即可

  解题代码：

  class Solution {
    public void moveZeroes(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count++;
            } else {
                nums[i - count] = nums[i];
            }
        }
        for (int i = nums.length - 1; i >= 0 && count > 0; i--, count--) {
            nums[i] = 0;
        }
    }
  }

  运行结果：

  

  复杂度分析：

• 时间复杂度：O(n)，出现了两个平级的 for 循环

• 空间复杂度：O(1)，没有额外数组

  引发的思考：

  类似这样的题目如果在没有额外限制的情况下是比较简单的，那在没有思路的情况下，先抛开限制，实现功能，然后加入限制条件进行优化尝试（方案二是在方案一的基础上重构而来的）；
  当然，类似的题目如果做的多了，一上来可能就想到了方案二，所以还是要多加锻炼才行呐~