runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: two pointer

Remove Element

📖 description

給定一個數值陣列 nums ，與需要刪除的數字 val ，實作 c++ 的 remove ，將數字擺到陣列後方並回傳剩下的元素。

🧠 solution

這題有個重點是我們可以修改原始陣列的順序，並且要求空間複雜度為 O(1) ，所以使用額外空間的直接方法沒有效，但其實可以換個想法，因為我們只需要把要刪掉的元素放到後面就好。
所以可以維護一個右指標，負責指向下一個被刪除的元素需要擺放的位置，再使用一個左指標指向當前看到的元素，此時有兩種可能

  • case 1 : 左指標看到的不是 val
    • 不用做事
  • case 2 : 左指標看的的是 val
    • 將數值與右指標的位置互換，且右指標往左走，直到當前位置不是 val

最後回傳 右指標+1 的位置就是還剩下多少元素了 

ex.
    要刪除 3

    1. round 1 (swap)

        |     |   
        3, 2, 2, 3
    
    2. round 2 (左右指標接觸，結束)

        |  |   
        2, 2, 3, 3

⏳ time complexity

遍歷一次陣列，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int l = 0, r = nums.size()-1;
        while(r>=l){
            if(nums[r]==val){   // 當前右指標的位置是要背刪除的元素，往左走
                r--;
            }
            else{
                if(nums[l]==val){   // 當前左指標的位置是需要被刪除的元素
                    swap(nums[l],nums[r]);
                }
                l++;
            }
        }
        return r+1;
    }
};