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

Analysis:

do not need to shift all the left arrays when duplication appears, simply add to the following one by one.

Lesson Learned:

int i = 3;
int a = i++; // a = 3, i = 4
int b = ++a; // b = 4, a = 4

i++ and ++i are very similar but not exactly the same. Both increment the number, but ++i increments the number before the current expression is evaluted, whereas i++ increments the number after the expression is evaluated.

• array缩小从小到大，array变大从大到小
• array缩小的过程可以不用多一个循环，直接比较存进array，用一个值记录

Code:

First attempt, very very slow(2%)

public class Solution {
    public int removeDuplicates(int[] nums) {
        // edge case
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int l = nums.length;
        int count = 0;
        while (count < l - 1) {
            if (nums[count] == nums[count + 1]) {
                for (int i = count; i < l - 1; i++) {
                    nums[i] = nums[i + 1];
                }
                l--;
            } else {
                count++;
            }
        }
        return l;
    }
}


public class Solution {
    public int removeDuplicates(int[] nums) {
        // edge case
        if (nums == null || nums.length == 0) {
            return 0;
        }

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

        }
        nums[count] = nums[l-1];
        count++;
        return count;
    }
}

Finally: time complexity: O(N), space complexity: O(1)

public class Solution {
    public int removeDuplicates(int[] nums) {
        // edge case
        if (nums == null || nums.length == 0) {
            return 0;
        }

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