leetcode-283-Move Zeroes

题目描述:

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: 
Output: [0,1,0,3,12][1,3,12,0,0]

Note:

  1. You must do this in-place without making a copy of the array.
  2. 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。

相关文章
相关标签/搜索