Leetcode一百题——移动零

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

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

示例 1:

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

示例 2:

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

提示:

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

我首先想到的是双指针解法

移动零（朴素双指针/主动搜寻法）

1. 算法核心思想

这套解法的核心思想是**“主动出击，缺啥找啥”**。 我们不改变原有的数组大小，而是通过两个指针（front 和 back）分工合作：

• front 就像是一个质检员，按顺序一个一个检查数组里的元素。
• 一旦 front 发现当前位置是 0（这是一个应该被踢到后面的坏蛋），它就原地停下，派出巡逻兵 back 往后去寻找第一个“非 0”的正常数字。
• back 找到后，把“非 0”数字和 0 交换位置，危机解除，front 继续往后检查。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int front = 0;
        int back = 0;
        
        // front 质检员开始从头到尾遍历数组
        while (front < nums.size()) {
            if (nums[front] == 0) {
                // 发现 0！派出 back 从 front 的下一个位置开始往后找非 0
                back = front + 1;
                
                // 加上边界保护，防止 back 跑出数组
                while (back < nums.size() && nums[back] == 0) {
                    back++;
                }
                
                // 如果 back 跑到尽头都没找到非 0，说明后面全是 0 了，直接收工
                if (back == nums.size()) {
                    break;
                }
                
                // 找到了非 0，交换两个人的位置
                int temp = nums[back];
                nums[back] = nums[front];
                nums[front] = temp;
                
                // 当前坑位填上了正常数字，front 可以继续前进了
                front++;
            }
            else {
                // 如果是正常数字，front 直接放行
                front++;
            }
        }
    }
};

3. 复杂度深度剖析

• 空间复杂度：O(1)。只额外使用了 front、back 和 temp 几个变量，完全是在原地操作，没有申请新的数组，完美符合题目要求。

• 时间复杂度：最坏情况下是 O**(n2)**。

  • 为什么是 O**(n2)？** 假设数组是 [0, 0, 0, 0, 1]。当 front 在第 0 位时，back 要跑 4 步去末尾找 1；交换后，当 front 在第 1 位时，back 又要从第 2 位开始重新往后跑到末尾……每一次 back 都会被重置到 front + 1，导致有些 0 会被反复检查多次。不过，由于题目数据规模是 104，这套解法在 C++ 中跑起来依然是可以过关的。