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

这道题是之前那道 Remove Duplicates from Sorted Array 有序数组中去除重复项 的延续,这里允许最多重复的次数是两次,那么我们就需要用一个变量count来记录还允许有几次重复,count初始化为1,如果出现过一次重复,则count递减1,那么下次再出现重复,快指针直接前进一步,如果这时候不是重复的,则count恢复1,由于整个数组是有序的,所以一旦出现不重复的数,则一定比这个数大,此数之后不会再有重复项。理清了上面的思路,则代码很好写了:

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (n <= 2) return n;
        int pre = 0, cur = 1, count = 1;
        while (cur < n) {
            if (A[pre] == A[cur] && count == 0) ++cur;
            else {
                if (A[pre] == A[cur]) --count;
                else count = 1;
                A[++pre] = A[cur++];
            }
        }
        return pre + 1;
    }
};

本文转自博客园Grandyang的博客,原文链接:有序数组中去除重复项之二[LeetCode] Remove Duplicates from Sorted Array II ,如需转载请自行联系原博主。

相关文章
|
5天前
|
存储 算法 数据挖掘
LeetCode 题目 88:双指针\直接\递归\插入排序\归并排序 实现合并两个有序数组
LeetCode 题目 88:双指针\直接\递归\插入排序\归并排序 实现合并两个有序数组
|
5天前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
5天前
|
SQL 算法 数据可视化
LeetCode第26题:删除排序数组中的重复项
LeetCode第26题:删除排序数组中的重复项
|
10天前
|
存储 算法 Java
【经典算法】LeetCode 26. 删除有序数组中的重复项:(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 26. 删除有序数组中的重复项:(Java/C/Python3实现含注释说明,Easy)
8 2
|
18天前
|
存储 搜索推荐
题目----力扣--合并两个有序数组
题目----力扣--合并两个有序数组
16 0
|
24天前
|
存储 搜索推荐 C语言
Leetcode—合并两个有序数组—C语言
Leetcode—合并两个有序数组—C语言
|
1月前
|
Python
使用array()函数创建数组
使用array()函数创建数组。
24 3
|
1月前
|
JavaScript 前端开发
总结TypeScript 的一些知识点:TypeScript Array(数组)(下)
一个数组的元素可以是另外一个数组,这样就构成了多维数组(Multi-dimensional Array)。
|
1月前
|
存储 JavaScript 前端开发
总结TypeScript 的一些知识点:TypeScript Array(数组)(上)
数组对象是使用单独的变量名来存储一系列的值。
|
1月前
|
存储 安全 Swift
在Swift中,数组(Array)
在Swift中,数组(Array)
35 3