2014年10月26日星期日

[Leetcode] Remove Duplicates from Sorted Array II

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].
The same idea with the former one, also use two pointer, and sweep all duplicate elements, use a count to check if we have duplicate, if we have, then just make a copy of that duplicate.
    public int removeDuplicates(int[] A) {
        int n = A.length;
        if(n < 3)
            return n;
        int p1 = 0, p2 = 1;
        
        while(p2 < n) {
            int cnt = 1;
            while(p2 < n && A[p2] == A[p1]) {
                p2++; cnt++;
            }
            if(cnt >= 2) {
                p1++;
                A[p1] = A[p1-1];
            }
            if(p2 == n) break;
            p1++;
            A[p1] = A[p2];
            p2++;
        }
        
        return p1+1;
    }

没有评论:

发表评论