【LittleDuck_LeetCodeNote】26 - Remove Duplicates from Sorted

更新於 2023/07/10發佈於 2023/07/10閱讀時間約 10 分鐘

【Instagram】 / 【巴哈姆特小屋】 / 【Vocus方格子】 / 【Medium】
喜歡的話就按個愛心或贊助ㄅ。

Question and Hints

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

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

Example 2:

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).

Constraints:

1 <= nums.length <= 3 * 104
100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

First Solution

💡 先確認好，我們的目標是要回傳k，即”有幾個不重複的數字” ，
以及在nums搜尋前k個數字時，可以得到不重複的結果。

我的思路是，用k去當作陣列尾的索引，
一旦遇到不重複的數字，就把他丟到陣列尾，
並且k最後的索引，即為整個不重複值陣列的長度。

陣列的第一個數字已經擺好了，所以不用管它，
我們要看第二個數字應該擺誰，
因此k從1開始，不斷和下一個值進行比較。

最後就能得到排列好的nums，以及不重複值的總數k。

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

        for(int i=0; i<nums.length-1; i++){
            if(nums[i] != nums[i+1]){
                nums[k++] = nums[i+1];
            }
        }

        return k;
    }
}

⏰ Runtime: 1 ms (99.95 %)

📦 Memory: 44.4 MB (28.90 %)

Upgrade Solution

clean up memory space.

💡 邏輯一樣，只是多了一個System.gc()的方法去回收沒有用到的陣列空間，
所以多了一點時間去清理記憶體，但占用的空間變小了。

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

        for(int i = 0; i<nums.length - 1; i++){
            if(nums[i] < nums[i+1]){
                nums[nextIndex] = nums[i+1];
                nextIndex++;
            }
        }
        System.gc();
        return nextIndex;
    }
}

⏰ Runtime: 6 ms (7.93 %)

📦 Memory: 42.3 MB (99.98 %)

Upgrade Solution 2

Use Hash’s feature : the same value across the same hash function, it will return the same result.

💡 LinkedHashSet 是Java一種陣列的儲存方式，
會將要輸入的值先透過Hash function轉換後，再存進陣列，
並且它不會儲存相同的內容，
所以將值存進LinkedHashSet ，就是在自動篩選掉重複的內容，
因此最後再將LinkedHashSet 的內容依序塞回nums，
回傳LinkedHashSet 的長度就好。

此方法由於使用的是LinkedHashSet，是一種LinkedList，
所以在操作元素時，不用像Array需要複製陣列再進行操作，
所以占用的空間會比較小。

class Solution {
    public int removeDuplicates(int[] nums) {

        //Insert all array element in the Set. 
        //Set does not allow duplicates and sets like LinkedHashSet maintains the order of insertion so it will remove duplicates and elements will be printed in the same order in which it is inserted

        LinkedHashSet<Integer> set = new LinkedHashSet<>();

        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }
        //copy unique element back to array
        int i = 0;

        for(int ele:set){
            nums[i++] = ele;
        }
        return set.size();
    }
}