Leetcode/各大家 -- 26.80. Remove Duplicates from Sorted Array (two ptr)

26.80 Remove Duplicates from Sorted Array (Two ptr)


easy & medium
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

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 in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

80. allowing 2 dup

What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

Microsoft Bloomberg Facebook

思路： Two pointer: i iterate array. j point to the 1st pos after end of the non-dup array, which is length

Use dup to track the last number in non-dup arrary. Till i find a number: nums[i] != dup, overwrite j with i and move j forward, update dup to nums[i]

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 1){return nums.length;}
        int dup = nums[0];
        int j = 1;//j point to the 1st post after last ele of non dup arr
        for(int i = 1; i < nums.length; i++){
            if(nums[i]!=dup){
                nums[j] = nums[i];
                dup = nums[i];
                j++;
            }
        }
        return j;
    }
}

思路： 2nd part, is just we need to keep 2 dup #, if nums[i] == dup1, it indicates there are >3 dups. Keep iterating until find a distinct nums[i] to dup1, update dup1 to dup2, and update dup2 to nums[i] 

eg: [0,0,1,1]

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 2) return nums.length;
        int dup1 = nums[0];
        int dup2 = nums[1];
        int j = 2;//point to 1st pos after last ele of non-dup arr = length
        for(int i = 2; i < nums.length; i++ ){
            if(nums[i] != dup1){//find the next distinct # to overwrite dup
                nums[j] = nums[i];
                j++;
                dup1 = dup2;
                dup2 = nums[i];
            }//else we have >=3 dup
        }
        return j;
    }
}