2014年4月20日 星期日

[LeetCode] 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 A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
Solution:O(n)
public class Solution {
    public int removeDuplicates(int[] A) {
        if(A == null || A.length ==0)
            return 0;
        int ret = 1;
        int curnum = A[0];
        int dup = 1;
        for(int i =1; i< A.length;i++){
            if(A[i] ==  curnum ){
                dup++;
            }else{
                dup = 1;
                curnum = A[i];
            }
            if(dup<3){
                    A[ret] = A[i];
                    ret++;
            }
        }
        return ret;
    }
}

沒有留言:

張貼留言