Leetcode — 26. Remove Duplicates from Sorted Array (中文)

問題連結: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

給予一個已排序的array, 把重複的數字移除,
結果需回傳這個沒有重複數字array的長度

限制: 需直接在給予的陣列改值, 不可另外創新的陣列

舉例來說 當 nums = [1,2,2,3,3,3,5,5] 
結果應回傳:4
且nums的前四個值應該長這樣: [1,2,3,5] (在這之後的是什麼值我們不在乎)

想法:

之前也做過很多類似要求in-place的題目, 我目前的發現是 很多都是靠兩個pointer就可以輕鬆解決 (不然就會需要一直swap, 時間複雜度也高)

程式邏輯:

程式碼的部分, 我就取兩個變數 i 跟 j
- j 是負責跑整個陣列
- i 則是保證指著"non-duplicated array"的最後一個element, 我們希望可以繼續拓展i, 直到我們不能再拓展

拓展i的條件就是 當nums[j]的值 不等於 nums[i]的時候 就可以把nums[j]加入我們這個non-duplicated array

也可以想成我們一直在覆蓋nums[i+1], 但也不用緊張說 這樣會不會覆蓋重要的資訊, 因為我們覆蓋的 都是我們在這個"non-duplicated array"裡面原本就有的值了

可以看看以下簡單例子:

For example, nums = [1,2,2]
i = 0 j = 0: since nums[j]==nums[i], 什麼都不用做, 只把j往右移
i = 0 j = 1: nums[j]!= nums[i], 我們可以拓展i了, 讓nums[j]加進我們的non-duplicated array裡
此時 nums = [1,2,2]. 把i跟j都往右移 
i = 1 j = 2: nums[j]==nums[i], 什麼都不用做, 只把j往右移
i = 1 j = 3: 完成
結果會回傳 i+1, 因為i是0-based的index, 我們需要回傳我們的non-duplicated array長度, 所以需再加1

以下為 贏過100% 的 0ms 程式碼:

public int removeDuplicates(int[] nums) {
        if(nums.length<=1)
            return nums.length;
        
        int count = 0;
        int i = 0, j = 0;
        int n = nums.length;
        while(j<n)
        {
            if(nums[j]!=nums[i])
                nums[++i] = nums[j];
            j++;
        }
        return i+1;
    }

時間複雜度: O(n)
空間複雜度: O(1) ✌️