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 =
» Solve this problem5
, and A is now [1,1,2,2,3]
.[解题思路]
加一个变量track一下字符出现次数即可,这题因为是已经排序的数组,所以一个变量即可解决。但是如果是没有排序的数组,可以引入一个hashmap来处理出现次数。
[Code]
1: int removeDuplicates(int A[], int n) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: if(n<=1) return n;
5: int pre=1, cur =1;
6: int occur = 1;
7: while(cur<n)
8: {
9: if(A[cur] == A[cur-1])
10: {
11: if(occur >=2)
12: {
13: cur++;
14: continue;
15: }
16: else
17: {
18: occur++;
19: }
20: }
21: else
22: {
23: occur = 1;
24: }
25: A[pre] = A[cur];
26: pre++;
27: cur++;
28: }
29: return pre;
30: }
Update 03/09/2014 improve readability a bit.
1: int removeDuplicates(int A[], int n) {
2: if(n == 0) return 0;
3: int occur = 1;
4: int index = 0;
5: for(int i =1; i< n; i++)
6: {
7: if(A[index] == A[i])
8: {
9: if(occur == 2)
10: {
11: continue;
12: }
13: occur++;
14: }
15: else
16: {
17: occur =1 ;
18: }
19: A[++index] = A[i];
20: }
21: return index+1;
22: }
No comments:
Post a Comment