搜索此博客

2013年2月7日星期四

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].
Hint, this problem looks easy, but quite tricky! The difficulty is to thing of all cases carefully! 1. You meet an old value, and it appears less than twice. 2. You meet a new value. 3. You meet a value which appears more than twice.

01 public int removeDuplicates(int[] A)      
02   //special case is handled first
03     if(A.length<=2)
04         return A.length;
05     int len=A.length;  
06     int value=A[0];
07     int curr=1;
08     int count=1;
09   
10     int i=1;
11     while(i<A.length)
12     {
13         //appearance of value less than twice, just copy, increment count
14         if(A[i]==value && count<2)
15         {              
16                 A[curr]=A[i];
17                 count++;
18                 curr++;
19               
20         }
21       
22         //new value, just copy, set new value, and set count back to 1
23         else if(A[i]!=value)
24         {
25             A[curr]=A[i];
26             value=A[i];
27             count=1;
28             curr++;
29           
30         }
31       
32         //value appear more than twice, skip it
33         else
34         {
35             len--;
36         }
37       
38         //After each iteration, i should increment by 1
39         i++;
40       
41     }
42   
43     //length of new array have been modified
44     return len;
45 }

没有评论:

发表评论