[Day 26] Leetcode 283. Move Zeroes (C++)

前言

TGIF!今天来个简单题休息一下~283. Move Zeroes。这题是要用inplace的方式来把0移到数列的後面。

想法

如果不管不要make a copy，简单的方式就是建立一个vector，遍历一遍原本的array，看到不是0的就把它push back到vector里，後面都补0就好了~
不过看到inplace不要make copy，第一个就想到swap的方式，想到的方法是遍历的时候看到是0的话就跟它後面第一个不是0的数做交换，所以一开始写了一个没有优化的版本，慢到看不到别的解法的车尾灯~

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // if 0, search for the next >0 integer
        for(int i=0;i<nums.size();++i){
            if(nums[i]==0){
                // search for the next elements not equal 0
                int j=i;
                while(nums[j]==0 & j<nums.size()-1){
                    ++j;
                }
                swap(nums[i],nums[j]);
            }
        }
    }
};

里面有些浪费时间的地方，例如说我每次都重新从i的地方开始找下个非0的数，但如果我前一次找到发现上一个非0已经远远在i的後面，就不用再从i开始找了，从上一个地方开始找就好，优化如下：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j=0;
        for(int i=0;i<nums.size();++i){
            if(nums[i]==0){
                // search for the next elements not equal 0
                j=max(j,i);
                while(nums[j]==0 & j<nums.size()-1){
                    ++j;
                }
                swap(nums[i],nums[j]);
            }
        }
    }
};

速度快了30倍左右。
附上另外一种解如下

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
       int j = 0;
       for(int i = 0; i < nums.size(); i++){
          if(nums[i] != 0)
          {
              swap(nums[i], nums[j++]);
          }
      }
  }
};

这个解法反过来是!=0的时候进行swap，为什麽可以这样做？其实它的j就是纪录目前非0个数(!=0就j++)，因此目前扫到的nums[i]就依序换到第j个非0个数的位置。