首页 > 代码库 > [C++]LeetCode: 72 Remove Duplicates from Sorted Array II

[C++]LeetCode: 72 Remove Duplicates from Sorted Array II

2024-10-25 20:18:02   210人阅读

题目：

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].

思路：

可以借鉴Remove Duplicates from Sorted Array的两个指针移动的方法。

不过需要考虑一些细节。比如，我们需要将小于3个的重复数字都不断往前赋值过去，超过3个才只移动point指针，向前搜索不等的数字。找到第三个我们才跳过，由于是有序数组，所以我们可以直接跟之前得到的数组（由 len 维护的数组）的前两位比较，即if A[point] == A[len-2], then A[point]==A[len-2]==A[len-1].这个数组维护的是一个重复数字最多为两个的数组。当不重复时，我们只是不断的将不重复的数字（或少于2）赋值到len维护的数组。同时移动len和point指针。重复超过2个时，我们只移动point，向前搜索不等的数字。

Attention:

1. 注意初始len 和 point取值。

int len = 2, itor = 2;
2. 注意我们无需计算个数少于3个的数组。

if (n <= 2) return n;
复杂度：O(N)

AC Code:

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n <= 2) return n;
        
        int len = 2, point = 2;
        while(point < n)
        {
            //如果A[point] != A[len-2],由于是有序数组，表示A[point] != A[len-1] && A[point] != A[len],即A[point]不是第三个重复数字
            //如果是则继续移动point,直到找到不等的数字，赋给A[len],len将停留在第三个重复数字的位置（如果有重复超过3个），将不超过3个的
            //重复数字赋值过来，len也跟着移动。
            if(A[point] != A[len-2])
                A[len++] = A[point];
            point++;
        }
        
        return len;
    }
};



[C++]LeetCode: 72 Remove Duplicates from Sorted Array II


联系
我们