leetcode-283-Move Zeroes

大故事家

2018-06-01

题目描述：

Given an arraynums, write a function to move all0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: <code>[0,1,0,3,12]</code>
Output: <code>[1,3,12,0,0]</code>

Note:

You must do thisin-placewithout making a copy of the array.
Minimize the total number of operations.

要完成的函数：

void moveZeroes(vector<int>& nums)

说明：

1、这道题给定一个vector，要求将vector中的0都移到vector的后面去，而把非0的数移到前面来，同时要求非0的数彼此之间的先后顺序不变。

要求尽可能减少操作的次数，同时只能在vector上变换，不能定义另一个vector。

2、这道题很明显就是要交换0和后面的非0数，所以最简单暴力的做法是双重循环。

外重循环不断地找0，每找到一个0就进入内重循环。

内重循环在找到的0的位置后面，搜索非0值，找到了就跟0交换。

代码如下，一个简单粗暴的双重循环。

void moveZeroes(vector<int>& nums) 
    {
        int i=0,s1=nums.size();
        while(i<s1)
        {
            if(nums[i]==0)
            {
                for(int j=i+1;j<s1;j++)
                {
                    if(nums[j]!=0)
                    {
                        swap(nums[j],nums[i]);
                        break;
                    }
                }
            }
            i++;
        }

上述代码实测24ms，beats 20.65% of cpp submissions。

3、改进：

上述代码至少有两个地方可以改进，如下：

①第二次进入内重循环浪费了第一次得到的信息，极大浪费时间。

假如vector是[0,0,0,0,1,2,3]，那么外重循环找到第一个0的位置是0，进入内重循环，一个个比较之后，找到第一个非0值的位置是4，交换位置。这一步没有任何浪费。

接着外重循环找到第二个0的位置是1，进入内重循环，又一个个比较，找到第二个非0值的位置是5，交换位置。这里的“又一个个比较”浪费了时间，明明在上一次已经比较过了，是可以知道中间这一部分是没有非0值的，还要一个个再比较一次。

这部分浪费了第一次得到的信息。

我们可以设置两个index，一个指向0值，一个指向非0值，这样就可以节省中间多次重复的比较。

详见下面代码。

②找不到非0值的时候没有停下来。

假如vector是[1,2,0,3,0,0]，我们找到第一个0的位置是2，进入内重循环，找到第一个非0值的位置是3，交换位置。接下来 i++，变成3。

然后接下来i=3这一位是0，又要进入内重循环，不断比较，然后i=4，又要进入内重循环，不断比较……直到最后 i 超过了vector的长度，结束循环。

所以我们其实找不到非0值的时候就要停下来，结束运行。这时候的vector就是最终结果了。

代码如下：（附详解）

void moveZeroes(vector<int>& nums) 
    {
        int i=0,j=0,s1=nums.size();//i表示0的位置，j表示非0的位置，两个index
        while(j<s1)
        {
            while(nums[i]!=0)//找到第一个0的位置，记录为i
                i++;
            if(j<i)//比如nums=[1,2,3,0,0,4]，前面的1/2/3都不用交换位置，j直接在i的下一位开始
                j=i+1;
            while(nums[j]==0&&j<s1)//找到第一个数值非0的位置，记录为j
                j++;
            if(j==s1)//如果找不到了，j已经在nums的外面了，就结束运行
                break;
            swap(nums[i],nums[j]);//如果还能找到满足条件的i和j，就交换位置
            i++;//更新i的值
            j++;//更新j的值
        }
    }

上述代码，改进了前面说的两个问题，实测16ms，beats 99.04% of cpp submissions。

vector