Skip to main content

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;
    }
}

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