[LeetCode] Remove Element (三種解法)
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
這題做下來感覺技巧性比較強，解出第一種解法以後我又嘗試了另外兩種解法，一個比一個簡單。。。我一開始卻折騰出了最晦澀的解法，可見一開始並沒有對題目有深刻的理解。
首先說說第一種解法，思路就是：維護一個表示“下一個交換位置”的指針ex，初始為-1。遍歷數組，當找到第一個elem的位置時，將ex指向他，
然後程序要做的就是在遍歷過程中檢查ex是否存在，存在的話就把當前數挪到ex處，同時把ex向前移動一位。
但是要注意一點是，當再次遇到elem時ex是不更新的。（也就是ex只是在elem第一次出現的時候為其賦值，然後就只用遞增他就行了）
復制代碼
int removeElement(int A[], int n, int elem) {
int ex = -1;
int len = n;
for (int i = 0; i < n; i++) {
if (A[i] == elem) {
len--;
if (ex < 0)
ex = i;
}
else if (ex >= 0) {
A[ex] = A[i];
ex++;
}
}
return len;
}
復制代碼
這個解法雖然略顯晦澀，但好處就是時間復雜度是O(n)，空間復雜度是O(1) ，算是一個比較理想的結果。
解法二：空間復雜度O(n)
使用額外的空間可以使思路變得簡單，要做的就是從A裡面逐一拷貝元素到aux裡，其中跳過elem就行了。缺點就是提升了空間復雜度，還有到最後需要把aux
的值在重新賦值給A，這樣時間復雜度也多了一倍到達了theta(2n)，空間復雜度為O(n)
復制代碼
int removeElement2(int A[], int n, int elem) {
int len = n;
int aux[n];
int k = 0;
for (int i = 0; i < n; i++) {
if (A[i] == elem) {
len--;
}
else {
aux[k++] = A[i];
}
}
for (int i = 0; i < len; i++) {
A[i] = aux[i];
}
return len;
}
復制代碼
解法三：認真觀察刪除操作的性質會發現，刪除一個元素不過就是把他後面的元素向前移動一位，那刪除兩個不就是移動兩位，三個就是三位。。。以此類推。
所以我們只用在遍歷數組的時候跟蹤刪除的個數n，然後同時將元素向後挪動n位就可以了，就這麼簡單。
復制代碼
int removeElement3(int A[], int n, int elem) {
int l = 0;
for (int i = 0; i < n; i++) {
if (A[i] == elem) {
l++;
}
else if (l > 0){
A[i-l] = A[i];
}
}
return n-l;
}
