Sunday, February 9, 2014

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:
Use Hash Map to record frequency, and put only elements into result array list when its frequency is one or two.

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A.length == 0) return 0;
        ArrayList results = new ArrayList();
        int arrayLength = 0;
        int times = 0;
        HashMap hash = new HashMap();
        for(int i = 0; i < A.length; i++){
            if(!hash.containsKey(A[i])){
                hash.put(A[i], 1);
                results.add(A[i]);
                arrayLength++;
            }
            else{
                times = hash.get(A[i]);
                times++;
                hash.put(A[i], times);
                if(times == 2) {
                    results.add(A[i]);
                    arrayLength++;
                }
            }
        }
        for(int i = 0; i < results.size(); i++){
            A[i] = results.get(i);
        }
        return arrayLength;
    }
}

No comments:

Post a Comment