Leetcode and Lintcode

Remove Duplicates from Sorted Array II

Problem:

Follow up for “Remove Duplicates”:
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.

Leetcode link
lintcode link

Solution:

Compared to Remove Duplicates from Sorted Array, We onlt need to add an another variable to record the number of times that the same elements occur, named as ‘same’;
This is a sorted map, so we just need to one variable to solve the problem, if not sorted, we need a Hashmap to record the occurrence of each elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*************************************************************************
	> File Name: RemoveDuplicate2.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com
	> Created Time: Thu 29 Oct 15:26:17 2015
 ************************************************************************/

public class RemoveDuplicate2{
    public int removeDuplicates(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0)
            return 0;
            
        int last = 0;
        int same = 0;
        for (int i = 1; i < nums.length; i++){
            if (nums[last] == nums[i])
                same++;
            else 
                same = 0;
            
            if (same < 2)
                nums[++last] = nums[i];
        }
        
        return ++last;
    }
}

Remove Duplicates from Sorted Array