[数据结构与算法]LeetCode 283. Move Zeroes

Given an integer array?nums, move all?0's to the end of it while maintaining the relative order of the non-zero elements.

Note?that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

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

最开始没注意到需要保持数组的相对顺序，就直接两个指针指向前后然后互换，跑了一下发现不对。后来也是看了答案才想到巧妙的做法，哎。

普通的做法就是先计算出有几个0，然后再开一个新数组，遍历一遍原数组把非0的放进来，最后把那几个0放到最后，并不是in place的做法，就不写了。

从solution抄来了一个思路，其实挺直观的，但被它讲复杂了而且自己也没想到……就直接是快慢指针，快指针指向当前遍历到的数字，慢指针保持它前面的都没有0，相当于用慢指针慢慢fill up快指针指向的非0元素，最后把慢指针后面的位置都填成0。

Runtime:?1 ms, faster than?100.00%?of?Java?online submissions for?Move Zeroes.

Memory Usage:?43.9 MB, less than?87.92%?of?Java?online submissions for?Move Zeroes.

class Solution {
    public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0;
        int curr = 0;
        while (curr < nums.length) {
            if (nums[curr] != 0) {
                nums[nonZeroIndex] = nums[curr];
                nonZeroIndex++;
            }
            curr++;
        }
        while (nonZeroIndex < nums.length) {
            nums[nonZeroIndex] = 0;
            nonZeroIndex++;
        }
    }
}

但是上面这种方法有一个弊端，就是在这个数组本来前面都大部分为0的时候，这一个个挪的就很费劲。?solution的第三种方法写的看着巨复杂，其实本质就是discussion的滚雪球做法，discussion里解释的比较巧妙且非常直观。?reference：Loading...

滚雪球的本质其实相当于是快慢指针，快指针是i，其实也就是当前遍历到的数字，我们要一直保持让它指向right most zero。如果它是0，那就多了一个0，直接count++；如果它不是0，说明这个数字应该和左边数第一个0交换，那也就相当于有一个慢指针指向left most zero，就是i - count。 看图会好理解很多，但是自己脑子里想又会开始绕弯弯……

Runtime:?9 ms, faster than?29.71%?of?Java?online submissions for?Move Zeroes.

Memory Usage:?55.1 MB, less than?18.59%?of?Java?online submissions for?Move Zeroes.

class Solution {
    public void moveZeroes(int[] nums) {
        int count = 0;
        // make i always point to rightmost 0 (or non 0 if no 0s)
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                // getting one more 0
                count++;
            } else {
                // nums[i] swap with nums[i - count]
                int temp = nums[i];
                nums[i] = 0;
                nums[i - count] = temp;
            }
        }
    }
}

如果真的写成快慢指针的话，和之前写的那版快慢指针对比一下，就相当于是在curr不为0的情况下，和最左的0进行交换（交换完了以后nonZeroIndex才是真正的非0，但是nonZeroIndex++以后，它又指向了下一个0，所以其实下面的代码应该重命名为leftMostZero最好吧）。现在脑袋还是有点晕乎乎，自己在草稿纸上画一下会好一些。以后再说吧。

Runtime:?5 ms, faster than?45.91%?of?Java?online submissions for?Move Zeroes.

Memory Usage:?54.4 MB, less than?74.62%?of?Java?online submissions for?Move Zeroes.

class Solution {
    public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0;
        int curr = 0;
        while (curr < nums.length) {
            if (nums[curr] != 0) {
                int temp = nums[curr];
                nums[curr] = nums[nonZeroIndex];
                nums[nonZeroIndex] = temp;
                nonZeroIndex++;
            }
            curr++;
        }
    }
}