我对一道常考面试题的详细分析

移动零

题目

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

示例:

输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数

分析

必须在原数组上操作，不能拷贝额外的数组；同时尽量减少操作次数，说白了就是想叫我们写出更好的算法。

如何分析？

观察

输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

整个过程就是0元素不断后移，非零元素不断前移的过程，所以算法每步操作的目标便是：逐渐达成这个分布规律。

怎样优化操作？

假设两个指针slow和fast分别指向连续零区间的第一个0，最后一个0的后一个位置，如下图所示：

那么，fast-slow 正是索引从0~fast区间范围内0元素的个数。

fast指向下一个元素：

若打问号元素为0，根据每步操作的目标是非零元素前移，零元素后移。所以迭代到此处时它已经为0元素，所以至少肯定不用前移，那么就保持原地不动。

若打问号的元素取值非0，根据每步操作的目标是非零元素前移，零元素后移。因为slow~fast这块都为0，所以为了目标，非零元素要和第一个0交换，这样不就实现非零元素前移，零元素后移的目标了吗

交换后：

你看确实前进一步了吧。

求解代码

以上分析过程就是此问题的一个中间状态的操作分析，是从第i次迭代状态到第i+1次迭代状态的变化过程。

有了这个状态更新方程，因此就会很自然的写出下面的代码：

class Solution(object):
    def moveZeroes(self, nums):
        fast,slow=0,0 # 分别指向连续零区间的最右侧、最左侧
        while fast<len(nums):
            # if nums[fast]==0 do nothing 
            if nums[fast]!=0:
                # if fast == slow shows zero isn't found yet
                if fast > slow:# zero exists
                    nums[slow], nums[fast] = nums[fast], 0
                slow += 1
            fast += 1   

S1，设定两个指针初始分别指向第一个元素：

S2，第一个元素等于0，仅fast前进1步：

S3, 下一次迭代时，fast指向元素不为0，则交换：

同时slow和fast同时都前进一步：

S4，此时元素等于0，此情况重复步骤S2，因此重复上面操作。

依次类推，罗列出中间的各个状态：

fast到头，程序结束。

可以看到slow指向连续零区间的第一个0，fast指向连续零区间的最后一个0的后一个位置。

这与文章中分析中间状态的过程一脉相承，验证分析过程是准确的。

Day1-Day35 刷题总结的思维导图