Remove Duplicates from Sorted Array 100

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.

Example

Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Solution

idea：从数组开头到nums[i]的所有数均为不重复的数。

i从0开始（第一个数），若遇到一个和第一个数不一样的数（即第二个数），则将i进一位并将nums[i]赋值为第二个数，依次类推，直到数组最后一个数。因此，共有i+1个数是不重复的数。

代码如下：

public class Solution {
    /**
     * @param A: a array of integers
     * @return : return an integer
     */
    public int removeDuplicates(int[] nums) {
        // write your code here
        if(nums == null || nums.length == 0){
            return 0;
        }

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

        return i + 1;
    }
}

Follwup Question

Follow up for "Remove Duplicates":

What if duplicates are allowed at most twice?

For example,

Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Solution

额外用一个boolean表示是否可以添加重复元素，只有boolean为true时才能添加重复元素。当添加一个新元素时，boolean设置为true，当添加一个重复元素后，boolean设置为false。

代码如下：

public class Solution {
    /**
     * @param A: a array of integers
     * @return : return an integer
     */
    public int removeDuplicates(int[] nums) {
        // write your code here
        if(nums == null || nums.length == 0){
            return 0;
        }

        boolean twice = true;
        int i = 0;
        for(int j = 1; j < nums.length; j++){
            if(nums[j] != nums[i]){
                i++;
                nums[i] = nums[j];
                twice = true;
            }else if(twice){
                i++;
                nums[i] = nums[j];
                twice = false;
            }
        }
        return i + 1;
    }
}