runtime 4 ms, beats 99.14% of cpp submissions
O(n) solution with explanation

tags: none

Remove Duplicates from Sorted Array

📖 description

給定一個 sorted array ，實作 c++ 內部函數 unique ，並要求空間複雜度為 O(1) 。

🧠 solution

因為是 sorted order ，所以我們不需要使用 hashmap 之類的結構來記憶不同項，因為只要發生左右值不對等的情形，代表右邊的那個值一定沒看過，所以只需要維護一個 pointer 指向我們目前看過幾格不同值來當 index 就解決問題了。

⏳ time complexity

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

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int now = 0;    //當前看到第幾個不同值
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i]!=nums[i+1]){     // 出現左右不同值
                now++;
                nums[now] = nums[i+1];  // 交換
            }
        }
        return now+1;
    }
};