刷題順序來自于cspiration。

#27 Remove Element

題目地址：https://leetcode.com/problems/remove-element/

初見 （O(n^2)復(fù)雜度）

初見過度依賴于C++的erase()這個函數(shù)，用這個函數(shù)把指定值的元素擦除，再在末尾用push_back()補一個0。需要建立兩個索引變量，其中一個用來控制循環(huán)次數(shù)，另外一個用來讀取數(shù)組元素。
代碼如下：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        int counter = 0;
        int ind = 0;
        for(auto it = 0; it < size; it++){
            if(nums.at(ind) == val){
                nums.erase(nums.begin()+ind);
                nums.push_back(0);
                counter++;
            }
                
            else
                ind++;
        }
        
        return size-counter;
    }
};

這個代碼雖然擊敗了98.42%的submissions，但是實際上性能怎么樣我自己還是心知肚明的。
erase()函數(shù)的時間復(fù)雜度最壞情況是O(n)，考慮到循環(huán)次數(shù)為n，總的復(fù)雜度應(yīng)該是O(n^2)。

Two Pointers（O(n)復(fù)雜度）

提示里有一個“Use two pointers"，想了半天也沒想出來是咋回事，怒看答案。答案的思路其實和初見版本已經(jīng)極其接近了，two pointers的意思估計就是兩個索引變量。只是對比初見版本的思路是擦除錯誤元素，這個算法的思路是留下正確元素：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        int counter = 0;
        int ind = 0;
        for(auto it = 0; it < size; it++){
            if(nums.at(it) != val){
                nums.at(counter) = nums.at(it);
                counter++;
            }
        }
        
        return counter;
    }
};

顯然覆蓋的時間復(fù)雜度是O(1)?？傮w時間復(fù)雜度是O(n)。雖然實際執(zhí)行時間同樣是4ms，但是這個算法顯然比第一個快得多。

交換(O(n)復(fù)雜度）

這個思想和初見其實一模一樣（本質(zhì)上都是交換），但是比起先擦除再插入，為什么不直接交換呢？

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        int counter = 0;
        int ind = 0;
        for(auto it = 0; it < size; it++){
            if(nums.at(ind) == val){
                iter_swap(nums.begin()+ind, nums.end()-1);
                nums.erase(nums.end()-1);
                counter++;
            }
                
            else
                ind++;
        }
        
        return size-counter;
    }
};

這次由于erase()只擦除最后一個元素，復(fù)雜度為O(1)，而iter_swap()復(fù)雜度也是O(1)，時間復(fù)雜度就為O(n)。
這個算法所需時間和前面的Two Pointers應(yīng)該是一致的，具體誰優(yōu)誰劣取決于實際上是要擦除的元素多還是要留下的元素多。值得一提的是這個算法擊敗了100%的submissions。

#26 Remove Duplicates from Sorted Array

初見 (O(n)復(fù)雜度）

和#27的Two Pointer思路一毛一樣。唯一要注意的就是這個爛鬼test case里還包含數(shù)組為空的情況。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        
        int size = nums.size();
        if(size == 0)
            return 0;
        int counter = 1;
        int temp = nums.at(0);
        for(int ind = 1; ind < size; ind++){ // Index starts from 1
            if(nums.at(ind) != temp){
                nums.at(counter) = nums.at(ind);
                temp = nums.at(ind);
                counter++;
                
            }
        }
        
        return counter;
    }
};

#80 Remove Duplicates from Sorted Array II

初見(O(n)復(fù)雜度）

這不就是#26的狀態(tài)機版本嘛，你也配medium？

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int size = nums.size();
        if(size == 0)
            return 0;
        int counter = 1;
        int temp = nums.at(0);
        int state = 1;
        for(int ind = 1; ind < size; ind++){ // Index starts from 1
            if(nums.at(ind) == temp && state == 2){
                // Do nothing
            }
            else if(nums.at(ind) == temp){
                state++;
                nums.at(counter) = nums.at(ind);
                counter++;
            }
            else{
                state = 1;
                nums.at(counter) = nums.at(ind);
                temp = nums.at(ind);
                counter++;
            }
        }
        return counter;
    }
};