LeetCode: Remove Element

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.

方案一

這個題目我首先想到的方案是：從前往後遍歷，將依次出現的目標用數組尾部不是目標的元素替換，因為題意明確指出元素順序可以改變。

具體實現方法是：設置兩個迭代器，一個用來前向掃描，一個用來後向掃描，前向掃描找到下一個目標，後向掃描找到最後那個非目標元素，二者交換（實際上無需交換，只需將最後那個元素賦給前向目標地址即可，因為題意明確指出超出新長度部分的元素不用管）。如此循環直至兩迭代器相逢。

具體代碼如下：

C++ codeclass Solution {
public:
    int removeElement(int A[], int n, int elem) {
        int forwardScan = 0, backwardScan = n - 1;
        while (forwardScan <= backwardScan)
        {
            if      (A[forwardScan  ] != elem) forwardScan ++;
            else if (A[backwardScan ] == elem) backwardScan--;
            else     A[forwardScan++] =      A[backwardScan--];
        }

        return backwardScan + 1;
    }
};

方案二

在Discuss裡面看到一種解決方案跟上面的類似，但是實現方法有兩點區別：

• 無需再用一個後向迭代器，直接用數組長度n即可；
• 無需從後面找到最後那個非目標元素，直接以之替換前向目標元素，下一次仍然從該元素開始掃描即可。

  具體實現方法如下：

  C++ codeint removeElement(int A[], int n, int elem) {
      int i = 0;
      while (i < n) {
          if (A[i] == elem) A[i] = A[(n--) - 1];
          else i++;
      }
      return n;
  }
  

  方案三

  在Discuss裡面還看到另外一種解決方案：無需使用後向迭代器，直接將非目標元素往前挪，覆蓋掉所有目標元素即可。

  這種方法有利有弊：

  • 缺點：挪動了大量元素，如果第一個元素就是目標的話，那麼整個數組都需要重新賦值；
  • 優點：保證了原來數組的順序。

    具體實現方法如下：

    C++ codeint removeElement(int A[], int n, int elem) {
        int begin=0;
        for(int i=0;i