2019-01-25 第一天 (#27, #26, #80)

刷题顺序来自于cspiration。

#27 Remove Element

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

初见 （O(n^2)复杂度）

初见过度依赖于C++的erase()这个函数，用这个函数把指定值的元素擦除，再在末尾用push_back()补一个0。需要建立两个索引变量，其中一个用来控制循环次数，另外一个用来读取数组元素。
代码如下：

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()函数的时间复杂度最坏情况是O(n)，考虑到循环次数为n，总的复杂度应该是O(n^2)。

Two Pointers（O(n)复杂度）

提示里有一个“Use two pointers"，想了半天也没想出来是咋回事，怒看答案。答案的思路其实和初见版本已经极其接近了，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;
    }
};

显然覆盖的时间复杂度是O(1)。总体时间复杂度是O(n)。虽然实际执行时间同样是4ms，但是这个算法显然比第一个快得多。

交换(O(n)复杂度）

这个思想和初见其实一模一样（本质上都是交换），但是比起先擦除再插入，为什么不直接交换呢？

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()只擦除最后一个元素，复杂度为O(1)，而iter_swap()复杂度也是O(1)，时间复杂度就为O(n)。
这个算法所需时间和前面的Two Pointers应该是一致的，具体谁优谁劣取决于实际上是要擦除的元素多还是要留下的元素多。值得一提的是这个算法击败了100%的submissions。

#26 Remove Duplicates from Sorted Array

初见 (O(n)复杂度）

和#27的Two Pointer思路一毛一样。唯一要注意的就是这个烂鬼test case里还包含数组为空的情况。

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)复杂度）

这不就是#26的状态机版本嘛，你也配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;
    }
};