Sunday, December 30, 2012

[LeetCode] 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].
» Solve this problem


[解题思路]
加一个变量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: