Leetcode-283-移动零

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

例如， 定义 nums = [0, 1, 0, 3, 12]，调用函数之后，nums 应为 [1, 3, 12, 0, 0]。

注意事项:

必须在原数组上操作，不要为一个新数组分配额外空间。
尽量减少操作总数。

---

分析：

题目不难理解，把非0元素向前移动，把0向后移动。最后让数组的前段都是原顺序的非零元素，数组后段都是0即可。题目要求不能创建新数组，那么需要想办法在原数组上下功夫。

下面给出两种解法：

解法一：

仔细分析题意，可以遍历数组，如果遇到0，那么和右边的第一个非零元素进行交换，然后再判断下一个元素是否为0。类似于冒泡的行为。这种方法注重移动元素的过程，时间复杂度高，速度慢！
Java解答如下：

    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                j = i + 1;
                while (j < nums.length) {
                    if (nums[j] != 0) {
                        nums[i] = nums[i] ^ nums[j];
                        nums[j] = nums[i] ^ nums[j];
                        nums[i] = nums[i] ^ nums[j];
                        break;
                    }
                    j += 1;
                }
            }
        }
    }

---

解法二：

仔细观察运行之后的结果，我们可以发现，不需要管中间移动的过程，只关注最终的结果即可。只要把数组中所有的非零元素，按顺序给数组的前段元素位赋值，剩下的全部直接赋值0，一切都OK了。这种方法时最快的！

Java解答如下：

    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index] = nums[i];
                index += 1;
            }
        }
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
    }