Leetcode 26. Remove Duplicates from Sorted Array

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.

解题思路：

没想明白，看的答案。用双指针，一个指针只记录unique的并且帮助记录长度，一个指针往前找。

This method returns the number of unique elements, but does not change the original array correctly. For example, if the input array is {1, 2, 2, 3, 3}, the array will be changed to {1, 2, 3, 3, 3}. The correct result should be {1, 2, 3}. Because array's size can not be changed once created, there is no way we can return the original array with correct results.

Java code:

public int removeDuplicates(int[] nums) {
        if(nums.length < 2){
            return nums.length;
        }
        int i = 0, j = 1;
        while(j < nums.length){
            if(nums[j] == nums[i]){
                j++;
            }else{
                i++;
                nums[i] = nums[j];
                j++;
            }
        }
        return i+1;
    }

2. 九章算法答案 2016.01.18

public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int size = 0;
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[size]) {
                nums[++size] = nums[i];
            }
        }
        return size + 1;
    }
}

Reference:

1. http://www.programcreek.com/2013/01/leetcode-remove-duplicates-from-sorted-array-java/

2. http://www.jiuzhang.com/solutions/remove-duplicates-from-sorted-array/