[LeetCode] 26. Remove Duplicates

</br>

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.

Solution

Since the array is sorted, the standard non-repeated array should be like.

nonRepeatedNums = [1,2,5,7,9,...]

Compared with the original array,

nums = [1,2,2,5,5,7,9,9,...]

We can clearly find out that if the array is sorted, the index should be smaller than its value as the most standard sorted array should be [1,2,3,4,5,6,7,8,9,...] , and if other array has index bigger than its value, there must be replicate numbers before itself.

This should be somewhat practical but still not easy enough to implement code.

Hence, we only have to compare the array with the ones that is already identified as non-repeated, once identified as a new non-repeated number, we can put this number in the array.

Instead of taking care of every element in the array, we only have to overwrite the front part of the array every time we identify a non-repeated number.

The code should do the rest explaining.

Java

public class Solution {
    public int removeDuplicates(int[] nums) {
        
        int i = nums.length>0 ? 1:0;
        
        for (int n : nums)
            if (n > nums[i-1])
                nums[i++] = n;
                
        return i;
    }
}

</br>