Wednesday, March 11, 2015

80. Remove Duplicates from Sorted Array II Leetcode Java

80. Remove Duplicates from Sorted Array II Leetcode
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:
Follow up for 

26. Remove Duplicates from Sorted Array Leetcode


An additional counter is needed to track the numbers of duplicates, once the counter is greater than 2, do not increment the index until a new value occur. 
Time complexity: O(n)
 public int removeDuplicates(int[] A) {  
    if(A==null) return 0;  
    if(A.length<=2) return A.length;  
    int count=1;  
    int ind=1;  
    for(int i=1;i<A.length;i++){  
      if(A[i]==A[i-1]) {  
         count++;  
        if(count<3) A[ind++]=A[i];  
      }  
      else {  
        A[ind++]=A[i];  
        count=1;  
    }  
    }  
   return ind;  
   }  

No comments:

Post a Comment