Easy
Related Topics: Array / Two Pointers
LeetCode Source

解題想法

這題有 Hint 我有看一下 XD
又是 Two pointer 的問題

• 一個 pointer i 指向每一個尋訪的數字
• 另一個 pointer index 則指向要被替換的數字

這裡我透過一個資料結構 bag 來儲存唯一的數字，但不符何題目所說的 in-place :(

演算法大致是透過尋訪所有值確認實際上有哪些值被存在 nums
如果發現沒有在 bag 裡頭則，用 bag 儲存
並將 index 指向的元素替換成 i 指向的元素

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        bag = []
        index = 0
        for i in range(len(nums)):
            if nums[i] not in bag:
                bag.append(nums[i])
                nums[index] = nums[i]
                index += 1
        return index

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int index = 0;
        vector<int> bag;
        for (int i = 0; i < nums.size(); i++) {
            if (std::find(bag.begin(), bag.end(), nums[i]) == bag.end()) {
                bag.push_back(nums[i]);
                nums[index] = nums[i];
                index += 1;
            }
        }
        return index;
    }
};

這裡有透過 C++ 的 standard library 中的 std::find

大致上是跟 Python 中 in 中的功能很像
如果沒有找到 vector 中的元素，則會回傳尋訪到的最後一個元素
這裡是回傳 vector 中的 bag.end()

附上二月多寫的版本，當時演算法效率比上面的好

解題想法

由於 1 <= nums.length <= 3 * 104，所以可以從第二個項目開始看
這裡我們一樣有兩個 pointer

• res 計錄要被替換的值的位置
• i 則是紀錄每個被尋訪的值

不過重點是尋訪判斷重複值的演算法
藉由比較右邊一位值的相同是否來判斷是否有出現不同值
但也要記得 for loop 的邊界要減一

如果發現右邊出現不同值
則將 res 的值替換成 i+1
且 res += 1

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        res = 1
        for i in range(len(nums) - 1):
            if nums[i] != nums[i+1]:
                nums[res] = nums[i+1]
                res += 1
        return res

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int res = 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] != nums[i+1]) {
                nums[res] = nums[i+1];
                res += 1;
            }
        }
        return res;
    }
};

這系列文被記錄在 Top Interview 150 Series