Leetcode 26. Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array :

題目的要求是輸入一個由小到大排序的陣列，我們需要回傳『沒有重複元素陣列長度』，並將這些沒有重複的元素移動至該陣列的開頭。

時間複雜度: O(n)

空間複雜度: O(1)

Python

方法一 :

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count=0
        i=1
        for i in range(len(nums)):  
            if(i==0 or nums[i]!=nums[i-1]):    #前後兩位數不相等時
                nums[count]=nums[i]            #給nums[count]值
                count+=1                       #計數幾個不同數
        return count

方法二 :

類似的方法，只是從紀錄非重複的，變成紀錄重複的數量

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

C++

雙指針:

初始index 為 0，i 開始遍歷，若發現 nums[i] 和 nums[i-1] 不相等，則說明找到新的元素，nums[index] 賦值為 nums[i]。index向後移動直到末尾。

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

        return index;
    }
};