题目

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

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

示例 1:

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

示例 2:

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

提示:

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

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

我的题解

思路一：类冒泡排序

从前往后遍历，如果遇到0，通过类似冒泡排序的方式不断向后两两交换位置，因为题目要求的原地完成操作。但是调换后数组发生了改变，这里使用一个单独的变量k控制当前正观察的变量，如果当前观察的为0，它调换到了后面，则观察的idx不需要改变；用变量i控制总循环次数为5次。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int k=0;
        for(int i=0;i<nums.size();i++){
            if(nums[k]==0){
                for(int j=k;j<nums.size()-1;j++){
                    int t = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = t;
                }
            }
            else{
                k++;
            }
        }
    }
};

问题：调换的次数还有优化的空间：当0特别多的时候。

我的双指针方法（实际只是上面方法的优化）

class Solution {
private:
    void swap(auto a, auto b){
        int t = *a;
        *a = *b;
        *b = t;
    }
public:
    void moveZeroes(vector<int>& nums) {
        auto head=nums.begin(), tail=nums.end();
        while(head!=tail){
            auto p = head;
            if(*p==0){
                while(p!=tail-1){
                    swap(p,p+1);
                    p++;
                }
                tail--;
            }
            else{
                head++;
            }
        }
    }
};

正确思路：

本质上是将非零元素向左调换位置，调换到对应的位置上，这样就好理解了。没有冒泡的逐个调换位置，而是直接到对应位置。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int src = 0, tar = 0;
        while(src!=nums.size()){
            if(nums[src]!=0){
                int t = nums[src];
                nums[src] = nums[tar];
                nums[tar] = t;
                tar++;
            }
            src++;
        }
    }
};

完成时间

2024-02-13：耗时【未记录】

题目链接

https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked