leetcode 之 move zeros

╰半夏微凉° 2022-12-17 13:58 105阅读 0赞

问题来源：[move zeros][]  
问题描述：给定一个数组，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。  
看到该问题第一个感觉很easy啊，抬手就来：

void moveZeroes(vector<int>& nums) {
        
        int start=0,end=nums.size()-1;
        while(start<end)
        {
        
            while(start<end&&nums[start]!=0) start++;
            while(start<end&&nums[end]==0) end--;
            swap(nums[start],nums[end]);
        }
    }

一运行居然错了，看输出结果一下明白过来了：上面的代码虽然把非0整数和0区分开了但是没有保证非0整数是顺序，还得重新构思。  
要保持非0元素的相对顺序还只能从一侧遍历，一种思路是将遍历中遇到的0往后移，每遇到一个0就找一个非0与之交换，按照这个思路代码实现如下：

void moveZeroes(vector<int>& nums) {
        
        int zeroIdx=0,nonZeroIdx;
        
        while(zeroIdx<nums.size())
        {
        
            while(zeroIdx<nums.size()&&nums[zeroIdx]!=0) zeroIdx++;
            nonZeroIdx=zeroIdx+1;
            while(nonZeroIdx<nums.size()&&nums[nonZeroIdx]==0) nonZeroIdx++;
            
            if(nonZeroIdx>=nums.size()) return;
            
            swap(nums[zeroIdx],nums[nonZeroIdx]);
            
            zeroIdx++;
        }
    }

上述代码一提交居然需要32ms，在超时的边缘徘徊，肯定有哪地方写得不好。如果仔细分析就会发现，当我们找到一个0元素之后都需要从该位置的下一个位置开始寻找非0元素。如果数组中的0元素很多，很大概率当前0元素的下一个位置还是0，我们还得重新遍历一遍0元素。这就启发我们不用每次都从当前位置的下一个位置开始遍历，而是从遍历到的非0元素的下一个位置开始遍历，这样就可以大大降低重复遍历的次数，按照这种逻辑修改上面的代码如下：

void moveZeroes(vector<int>& nums) {
        
       int zeroIdx=0,nonZeroIdx=1;
        
        while(zeroIdx<nums.size())
        {
        
            while(zeroIdx<nums.size()&&nums[zeroIdx]!=0) zeroIdx++;
            if(nonZeroIdx<zeroIdx) nonZeroIdx=zeroIdx+1;
            while(nonZeroIdx<nums.size()&&nums[nonZeroIdx]==0) nonZeroIdx++;
            
            if(nonZeroIdx>=nums.size()) return;
            
            swap(nums[zeroIdx],nums[nonZeroIdx]);
            
            zeroIdx++;
            nonZeroIdx++;
        }
    }

上述代码提交之后运行需要12ms，超过了50%的用户，虽然有进步但感觉还是不够快。一时半会也没想到啥新的思路就翻翻题解吧，看完题解真是整个人都不好了，这么简单的题目居然让我整得这么复杂，看看题解代码吧：

void moveZeroes(vector<int>& nums) {
        
        int nonZeroCount=0;
        for(auto n:nums)
        {
        
            if(n) nums[nonZeroCount++]=n;
        }
        for(int i=nonZeroCount;i<nums.size();i++)
        {
        
            nums[i]=0;
        }
    }

之前代码的思路是先找0再去找非0，而题解代码是先找非0，找到非0直接覆盖前面的位置，找完之后后面直接赋0，就这么简单，运行时间可以进一步降低到8ms，超过92%的用户。无fuck说……

[move zeros]: https://leetcode-cn.com/problems/move-zeroes/