0026 - Remove Duplicates from Sorted Array

大意

給出一個由小排到大的整數陣列，把裡面重複的數字移除後，回傳陣列剩餘整數數量 K

一個示範的輸出輸入 case:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

個人想法

一開始誤會成「把 dupe 的數量回傳」但是後來看到 K 被用來當作邊界數，所以應該是要回傳「實際在處理陣列時，跑到的 count 數量」

也就是以下程式碼這樣（Java）：

class Solution {
    public int removeDuplicates(int[] nums) {
        int dupeCount = 0;
        int count = 0;

        // 有 dupe 的部份要把他算到結束邊界上
        while(count < nums.length - 1 - dupeCount){
            if(nums[count] == nums[count + 1]){
                // 如果發現前面有重複，移動到前面，dupe 數 + 1
                for(int j = count; j < nums.length - 1 - dupeCount; j++){
                    nums[j] = nums[j + 1];
                }
                dupeCount += 1;
            } else {
                count += 1;
            }
        }
        
        // 之前結束邊界扣 1 是為了避免 out-of-bound
        // 所以要再 + 1 才能表示原始數字
        return count + 1;
    }
}

不過這效率滿差的（會卡在把陣列移動到前面的狀況？或是兩層迴圈的問題...），不是 LeetCode 前段的執行時間。

後來看了 LeetCode 的討論，有一個只要一個迴圈的思考方式，就是計算 unique index，根據當前位置與前一個位置比較，如果遇到獨特的數，就把他複寫到當前的 unique index：

class Solution {
    public int removeDuplicates(int[] nums) {
        int uniqueIndex = 1;

        for(int i = 1; i < nums.length; i++){
            // 如果遇到不重複，把他複寫到 uniqueIndex 所在的位置
            if(nums[i] != nums[i - 1]){
                nums[uniqueIndex] = nums[i];
                uniqueIndex++;
            }
        }

        return uniqueIndex;
    }
}

這個時間複雜度就會減少很多了。

有時候可以做反向思考，而不是執著於題幹的描述，應該會對優化算法很有幫助。