Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
What if duplicates are allowed at most twice?
For example,
Given sorted array A =
Given sorted array A =
[1,1,1,2,2,3],
Your function should return length =
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.5, and A is now [1,1,2,2,3].
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 }
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 }
没有评论:
发表评论