Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Remove Duplicates from Sorted Array II

Leetcode algorithms 第 80 题: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].

解答

移除数组的重复元素,使得每个数字最多出现两次。由于数组已排序,从左到右遍历数组,如果当前数字和之前数字不一致,则直接输出并记录出现次数为1,如果一致,则判断出现次数是否小于2,如果是则输出并把出现次数加一,否则直接忽略。

具体代码如下:

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int id = -1, cnt = 0; //当前答案的下标,前一个元素出现的次数
        for (int i = 0; i < n; i++)
        {
            if (id == -1 || A[i] != A[id])
                A[++id] = A[i], cnt = 1;
            else if (cnt < 2) //相同时出现次数小于2才输出
                A[++id] = A[i], cnt++;
        }
        return id + 1;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论