Sunday, June 8, 2014

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

Solution:

public class Solution {
    public int removeDuplicates(int[] A) {
        int count = 0;
        int value = Integer.MIN_VALUE;
        int i = 0;
        int len = A.length;
        while (i<len)
        {
            if (A[i]==value)
                count++;
            else
            {
                count = 1;
                value = A[i];
            } 
            if(count>2)
                moveToEnd(A,i,--len);
            else
                i++;
        }
        return len;
    }
    
    private void moveToEnd(int[]A, int pos1, int end)
    {
        for(int i= pos1; i<end; i++)
            swap(A, i, i+1);
    }
    
    private void swap (int[] A, int pos1, int pos2)
    {
        int temp = A[pos1];
        A[pos1] = A[pos2];
        A[pos2] = temp;
    }
}

No comments :

Post a Comment