C++实现LeetCode(80.有序数组中去除重复项之二)

[LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],

Your function should return length =

5

, with the first five elements of

nums

being

1, 1, 2, 2

and 3 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length =

7

, with the first seven elements of

nums

being modified to 

0

, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

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

解法一:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int pre = 0, cur = 1, cnt = 1, n = nums.size();
        while (cur < n) {
            if (nums[pre] == nums[cur] && cnt == 0) ++cur;
            else {
                if (nums[pre] == nums[cur]) --cnt;
                else cnt = 1;
                nums[++pre] = nums[cur++];
            }
        }
        return nums.empty() ? 0 : pre + 1;
    }
};

这里其实也可以用类似于 Remove Duplicates from Sorted Array 中的解法三的模版,由于这里最多允许两次重复,那么当前的数字 num 只要跟上上个覆盖位置的数字 nusm[i-2] 比较,若 num 较大,则绝不会出现第三个重复数字(前提是数组是有序的),这样的话根本不需要管 nums[i-1] 是否重复,只要将重复个数控制在2个以内就可以了,参见代码如下:

解法二:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (int num : nums) {
            if (i < 2 || num > nums[i - 2]) {
                nums[i++] = num;
            }
        }
        return i;
    }
};

到此这篇关于C++实现LeetCode(80.有序数组中去除重复项之二)的文章就介绍到这了,更多相关C++实现有序数组中去除重复项之二内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-17

C++实现LeetCode(76.最小窗口子串)

[LeetCode] 76. Minimum Window Substring 最小窗口子串 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BA

C++实现LeetCode(75.颜色排序)

[LeetCode] 75. Sort Colors 颜色排序 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2

C++实现LeetCode(81.在旋转有序数组中搜索之二)

[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.

C++实现LeetCode(74.搜索一个二维矩阵)

[LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

C++实现LeetCode(79.词语搜索)

[LeetCode] 79. Word Search 词语搜索 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. Th

C++实现LeetCode(82.移除有序链表中的重复项之二)

[LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Outp

C++实现LeetCode(73.矩阵赋零)

[LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably

C++实现LeetCode(72.编辑距离)

[LeetCode] 72. Edit Distance 编辑距离 Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a char

LeetCode -- Path Sum III分析及实现方法

LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

Python实现计算最小编辑距离

最小编辑距离或莱文斯坦距离(Levenshtein),指由字符串A转化为字符串B的最小编辑次数.允许的编辑操作有:删除,插入,替换.具体内容可参见:维基百科-莱文斯坦距离.一般代码实现的方式都是通过动态规划算法,找出从A转化为B的每一步的最小步骤.从Google图片借来的图, Python代码实现, (其中要注意矩阵的下标从1开始,而字符串的下标从0开始): def normal_leven(str1, str2): len_str1 = len(str1) + 1 len_str2 = len

Python文本相似性计算之编辑距离详解

编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数.编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符.一般来说,编辑距离越小,两个串的相似度越大. 例如将kitten一字转成sitting:('kitten' 和 'sitting' 的编辑距离为3) sitten (k→s) sittin (e→i) sitting (→g) Python中的Levenshtein包可以方便的计算编辑距离

Ruby实现的最短编辑距离计算方法

利用动态规划算法,实现最短编辑距离的计算. 复制代码 代码如下: #encoding: utf-8 #author: xu jin #date: Nov 12, 2012 #EditDistance #to find the minimum cost by using EditDistance algorithm #example output: #  "Please input a string: " #  exponential #  "Please input the

基于Java实现杨辉三角 LeetCode Pascal's Triangle

Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =

ecshop 2.72如何修改后台访问地址

2.72版本之后修改后台登录地址非常方便,步骤如下: 1.修改 admin 文件夹名称为别人猜不到的,例如 ecshop 2.打开data/config.php文件 查找: 复制代码 代码如下: define('ADMIN_PATH','admin'); 修改为(把其中的 admin 修改为 ecshop ): 复制代码 代码如下: define('ADMIN_PATH','ecshop'); 3.这样访问 域名/ecshop 即可连接到后台. 是不是很简单呢,希望小伙伴们能够喜欢

Java动态规划之编辑距离问题示例代码

动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移.一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划. 动态规划实际上是一类题目的总称,并不是指某个固定的算法.动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法.动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解.而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题.问题描述: 对于序列S和T,

Java滚动数组计算编辑距离操作示例

本文实例讲述了Java滚动数组计算编辑距离操作.分享给大家供大家参考,具体如下: 编辑距离(Edit Distance),也称Levenshtein距离,是指由一个字符串转换为另一个字符串所需的最少编辑次数. 下面的代码摘自org.apache.commons.lang.StringUtils 用法示例: StringUtils.getLevenshteinDistance(null, *) = IllegalArgumentException StringUtils.getLevenshtei

vscode中配置LeetCode插件的教程(愉快刷题)

大家好,今早在B站看到up主的vscode里藏了leetcode插件,这才知道原来还有这款神器.但是没想到在用的时候遇到了一些麻烦,花了一点时间才解决.所以写这篇文章除了给大家安利这个好用的插件之外,也是为了帮助更多的同学避免踩坑. 简介vscode vscode在工业界鼎鼎大名,被誉为微软少有的拿得出手的精品(逃).原本是不想过多赘述的,但是鉴于许多粉丝还是正在上学的萌新,所以花点笔墨简单介绍一下. vscode是微软开发的编辑器,严格说起来它并不是一个IDE,只是一个编辑器.但是由于它支持嵌

vscode+leetcode环境配置方法

前言 之前安装anaconda3的时候,选择了同时安装vscode,但从来没有正式去接触过它.最近,偶然想到看看leetcode,发现在vscode上搞leetcode很方便,于是就开始倒腾起来了. vscode配置 如何安装我就不详述了,win/ubuntu下的安装可参见我的博客: vscode+python+c++ 我现在的vscode的版本是:1.43.1 需要安装的插件有: anaconda extension pack: 支持非python官方的三方库code runner:F5快捷运