MoveZeroes [source code]

public class MoveZeroes {
    public void moveZeroes(int[] nums) {
        int end = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) nums[end++] = nums[i];
        }
        for (int i = end; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

这个题目一把头搞定了最优解, 还是挺爽的, 0ms;

当然也可以一板一眼的做, 就是从0开始扫, 每次碰到一个0, 开起一个inner loop, 扫到第一个不是0的位置, 然后后面的全都向前移动, 与前面非0的部分接起来; 如果用 invariant 的观点来理解, 就是just before the beginning of iteration i, 0..i-1 are all non-zero elements;

当然更好的办法就是换一个想法: 这个题目的题目描述其实就是有点故意误导你从移动的角度来做. 但是因为这里的移动涉及的其实是一个given value, 所以用 assignment 其实也可以完成完全类似的功能;

这个思路的获取可能更有可能来自于: 想想一开始给你的是什么样的一个 array, 然后你最后得到的一个 array是什么样的, 通过对比来刺激大脑直接观察出两者之间的规律;

当然如果非要从技术层面来理解, 这里利用的一个 fact 就是point i moves faster than pointer end;

最优解基本和我这个代码一样, 不过人家开头还是有legitimacy check:

    if (nums == null || nums.length == 0) return;

Problem Description

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

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:49.42%
Contributor: LeetCode
Topics:
Array Two Pointers
You might like:
(E) Remove Element
Company:
Bloomberg Facebook