leetcode-80-删除排序数组中的重复项 II

2021-07-20 19:08

阅读：516

标签：比较 code 直接使用 div 排序五个 baidu 替换

题目描述：

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,1,2,3,3],

函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

你不需要考虑数组中超出新长度后面的元素。

要完成的函数：

int removeDuplicates(vector& nums)

说明：

1、这道题给定一个vector，里面存放着升序排列的int型整数。

这些整数可能有多个，比如[1,1,1,2,2,3,4,5,5,5,5,5]，要求每个整数只能出现2次，所以最终变成[1,1,2,2,3,4,5,5]。

为此你需要原地修改vector的数值，要求只能使用O(1)的空间。

最后返回新的vector的长度，不需要返回修改完的vector，但是vector要原地修改完成。

不需要在意修改完的vector后面的元素，测试样例在测试时只会在意你返回的长度以内的vector元素。

2、这道题从思路上来说，一点也不难，只是比较繁琐。

我们看一下举的这个例子，[1,1,1,2,2,2,3,3,3]

我们需要先找到第一个可以被替换的位置，第三个1，也就是位置是2。

然后找到第一个需要更换的位置，第一个2，也就是位置是3。

把第一个2放在第三个1那里。

接着继续往后面走，继续匹配。第二个2要放在第一个2的位置上，接着第三个2由于已经出现了两次了，所以不理。

到达下一个不一样的元素3，把3放在第二个2的位置上，把第二个3放在第三个2的位置上，最后的第三个3就不理了。

思路一点都不复杂，代码如下：（附详解）

    int removeDuplicates(vector& nums) 
    {
        int i=1,j=0,s1=nums.size(),count=1,t;
        if(s1==0)return 0;//如果vector中没有元素，返回0，不用修改vector
        else if(s1==1)return 1;//如果vector中只有1个元素，返回1，不用修改vector
        while(i2)//出现了第三次，那么break，当前i的位置就是第一个可以被后面元素替换的位置
                    break;
                i++;
            }
            else//如果不一样了，那么重新初始化count为1
            {
                i++;
                count=1;
            }
        }
        j=i+1;//要找到第一个需要替换的元素位置
        if(i==s1)return i;//边界条件，比如[1,2,3,4],i==s1，那么直接返回i
        if(j==s1)return i;//边界条件，比如[1,1,1],i=2，j=3，j==s1，那么直接返回i
        while(nums[j]==nums[i]&&j2)//如果出现了2次以上，那么我们需要找到跟t不一样的元素值的位置
                {
                    while(nums[j]==t&&j

上述代码实测12ms，beats 99.85% of cpp submissions。

这道题其实思路很简单，就是琐碎了点，需要测试各种边界条件。

leetcode-80-删除排序数组中的重复项 II

标签：比较 code 直接使用 div 排序五个 baidu 替换

原文地址：https://www.cnblogs.com/king-3/p/9516995.html

上一篇：spring data jpa 详解

下一篇：java设计模式

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：leetcode-80-删除排序数组中的重复项 II
文章链接：http://soscw.com/index.php/essay/106715.html

亲，登录后才可以留言！

leetcode-80-删除排序数组中的重复项 II

题目描述：

要完成的函数：

说明：

评论

热门文章

推荐文章

最新文章

置顶文章