📝 题目描述

题目链接：移动零

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

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

示例：

1
2
3
4
5
6
7
8
9
10

示例 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

💡 解题思路

方法一：暴力解法

遍历数组（ptr1），每当遇到一个0时，就停下来。然后启动一个内层循环（ptr2），从当前位置向后扫描，寻找第一个非零元素。找到后，将两者交换，保证非零元素被挪到前面，0被挪到后面。

缺点： 被动地“填坑”，发现一个0，赶紧去找个数来填上。

方法二：快慢指针解法

使用两个指针，

left（慢指针）： 维护非零数组的边界，含义是“下一个非零元素应该放置的位置”。

right（快指针）： 负责在前探路，遍历整个数组。

当right遇到非零数，就把它和left位置的数交换，然后left向前推进一步。如果right遇到0，则忽略，继续前行。

刚开始时，left=right，都是0。
如果数组是[0,1]，那么left刚开始指向0，right跳过0指向1，第一次交换后变为[1，0]；
如果数组是[1,0]，那么left刚开始指向1，right指向1，自我交换后还是[1，0]，此时left会+1，指向0，right也会指向0并继续工作。

优点： 主动地“收集”，不管0在哪，我只把非零的数按顺序往前排，0自然就被挤到后面去了。

🔧 代码实现

1、暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        for(int ptr1 = 0; ptr1 < n; ptr1++){
            if(nums[ptr1] == 0){
                for(int ptr2 = ptr1 + 1; ptr2 < n; ptr2++){
                    if(nums[ptr2] != 0){
                        nums[ptr1] = nums[ptr2];
                        nums[ptr2] = 0;
                        break;
                    }
                }
            }
        }
    }
};

2、快慢指针解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

📊 复杂度分析

1、暴力解法

  • 时间复杂度：O(n2)O(n^2)，假设数组是 [0, 0, 0, …, 0, 1]，对于前面的每一个 0，内层循环都要遍历整个数组去寻找那个1。
  • 空间复杂度：O(1)O(1)，在位交换，无额外开销。

2、快慢指针解法

  • 时间复杂度：O(n)O(n)，right 指针只从头到尾遍历了一次数组。每个元素最多被访问和处理一次。
  • 空间复杂度：O(1)O(1)，在位交换，无额外开销。

🎯 总结

  • 核心思想：跳出双重循环思想，使用分离的思想，两个指针各司其职