Remove Duplicates from Sorted Array

Question

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Solution

自己第一次寫的時候用了 extra space 才 AC，但第二次寫有寫出來。主要概念是快慢指針，當 nums[slow] == nums[fast] 時，讓快指針繼續走，等走到 nums[slow] != nums[fast] 時，慢指針進一步，然後兩者交換並更新長度即可

public int removeDuplicates(int[] nums) {
    if (nums.length == 0 || nums == null) {
        return 0;
    } else if (nums.length == 1) {
        return 1;
    }
    int slow = 0, fast = 1, res = 1;
    while (fast < nums.length) {
        if (nums[fast] == nums[slow]) {
            fast++;
        } else {
            slow++;
            nums[slow] = nums[fast];
            res++;
        }
    }
    return res;
}

Update

其實這題有一個 template 可以解：

public int removeDuplicates(int[] nums) {
    if (nums == null) {
        return 0;
    } else if (nums.length < k) {
        return nums.length;
    }

    int i = 1, j = 1, count = 1;
    while (j < nums.length) {
        if (nums[j] != nums[j - 1]) {
            count = 1;
            nums[i++] = nums[j];
        } else {
            if (count < k) { // 可容許 k 個 duplicates
                nums[i++] = nums[j];
                count++;
            }
        }
        j++;
    }
    return i;
}

看了一下，覺得要做到這種 in-place 然後又只有 O(1) 的 extra space，重要概念就是要有一個 index 從頭到尾慢慢 update，應該就有點類似慢指針，然後一律從 i = 1 開始 update 起。然後，感覺自己在做題時有點想的太複雜了