LeetCode Hot 100：283. 移动零

题目

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:‌

输入:‌ nums = [0,1,0,3,12] 输出:‌ [1,3,12,0,0]

示例 2:‌

输入:‌ nums = [0] 输出:‌ [0]

提示‌:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

进阶：‌你能尽量减少完成的操作次数吗？

题解

Go：

func moveZeroes(nums []int)  {
    slow := 0
    for fast := 0; fast < len(nums); fast ++ {
        if nums[fast] != 0 {
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow ++
        }
    }
}

双指针法分为两种：‌对撞双指针（头尾指针相向而行）和 快慢双指针（同向同轨而行）。‌

这个是典型的快慢双指针。一开始我尝试用两个 for 维护两个指针，用类似冒泡的方式来进行元素的交换（即交换的元素总相邻）；然而这个思路被证明是有问题的。冒泡的时间复杂度不可能太低。

破局的关键是意识到 0 的顺序总是无关紧要的。 还有，代码中快慢指针重合时交换自己这个行为虽然看起来让人困惑，但它在数学上的表意是：当快慢指针重合时什么都不做。事实上，当快慢指针不重合时，只需要让nums[slow] = nums[fast]; nums[fast] = 0即可（因为当两指针不重合时，slow 指针指向的应该是 0。

然而 Go 提供了非常方便的语法糖可以让我们在一行内完成变量值的交换而无需引入一个 tmp 变量。

王朝了有没有懂的？

Java：

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast ++) {
            if (nums[fast] != 0) {
                if (fast != slow) {
                    nums[slow] = nums[fast];
                    nums[fast] = 0;
                }
                slow ++;
            }
        }
    }
}

这是不无脑交换的版本。

记录

1. Go 中交换元素一行就够了。
2. 后面我忘了。