首页 > 代码库 > [leetcode]_Remove Duplicates from Sorted Array II

[leetcode]_Remove Duplicates from Sorted Array II

2024-07-06 00:51:16   224人阅读

题目：一个有序数组，要求保证数组中的每个元素不能超过2个。

　　  输入：A = [1,1,1,2,2,3]  输出：length = 5, and A is now [1,1,2,2,3]

 

思路：双指针 。有些绕，不过理清了后，思路还是很直接明朗的。

1、两个指针：p和help。初始化时同时指向数组头。变量cur记录当前元素值，count记录当前元素值出现的次数。

2、当 A[p] == cur && count < 2 或者 A[p] != cur 的时候，A[help] = A[p], help++ , p++。

3、当 A[p] == cur && count >= 2时，p++,help不动。

4、直到p指向尾部，此时help的值即为去重后的数组长度。

 

代码：

 1 public int removeDuplicates(int[] A) {
 2        if(A.length == 0) return 0;
 3        
 4        int cur = A[0] , count = 1;
 5        int help = 1;
 6        for(int p = 1 ; p < A.length ; p++){
 7            if(cur == A[p]){
 8                if(count < 2){
 9                    count++;
10                    A[help++] = A[p];
11                }
12            }else{
13                count = 1;
14                cur = A[p];
15                A[help++] = A[p];
16            }
17        }
18        return help;
19 }

 


联系
我们