26. 删除有序数组中的重复项

Leetcode题目:vector.erase&&双指…

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过,那么您的题解将被 通过。

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示:

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列

解题思路

真的要“删除”吗?

一开始以为真的是要删除,所以用了vector自带的erase去删除元素。本来还想用迭代器,但是发现没必要就没用了。思路的话…也没啥思路,erase删完元素后会自动帮你把后面的元素往前排。但是这就有个问题,待会提。

代码(使用erase)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
       int length=nums.size();
       for(int i=1;i<length;)
       {
           if(nums[i-1]==nums[i])
           {
               nums.erase(nums.begin()+i);
               length--;
           }else
           {
               i++;
           }
       }
       return length;
    }
};

这么做的后果就是,效率太低。就算用nums.shrink_to_fit();去释放内存(erase只会删除vector中的元素,不会释放该元素占用的内存)也没什么效果,耗时仍然达到480ms+。

所以我看了看官方题解,发现并不是要真的删除某个元素….实际上是把重复的元素往后排,不重复的元素往前排。举个例子。

  • 初始:[0,0,1,1,1,2,2,3,3,4]
  • “删除”:[0,1,2,3,4,2,2,3,3,4]

真的删了元素吗?如删。快慢指针的话也不难理解,时间复杂度毕竟还是O(n)。能不能看出来题目要求是“替换”而不是“删除”才是问题(我反正是没看出来🐒)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x