前言

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個數的位置。

結語

明天再回歸sum系列吧~