leetcode 之 move zeros

问题来源：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说……