Thursday, January 1, 2015

Remove Duplicates from Sorted Array II (LeetCode Array)

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

Idea: Use two pointers i, j. i points to the index of last valid number. Use j to scan the array from left to right. If num[i]==num[i-1]==num[j], "continue"; otherwise copy num[j] to num[++i].

Time: O(n) Space: O(1)

Code:
 public class Solution {  
   public int removeDuplicates(int[] A) {  
     if(A==null)  
       return 0;  
     if(A.length<=2)  
       return A.length;  
     int i=1;  
     for(int j=i+1;j<A.length;j++)  
     {  
       if(A[i]==A[i-1]&&A[i]==A[j])  
         continue;  
       else  
         A[++i]=A[j];  
     }  
     return i+1;  
   }  
 }  

No comments:

Post a Comment