在线客服免费_软件开发项目流程_seo技术培训沈阳_会计培训班的费用是多少

题目链接：

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

题目描述：

解题思路：

按照题目中要求，必须在原来数组中进行修改，并且在O(1)额外空间条件下完成。因此我们可以使用双指针算法，算法具体流程如下：

• 如果数组长度 nums.size() <= 2, 则直接 return nums.size()即可
• 定义两个指针 slow 和 fast，并初始化为2
• 如果 nums[slow - 2] == nums[fast]，说明已经有两个数相等，因此 nums[fast] 数值不能放进结果之中。反之，如果nums[slow - 2] != nums[fast]，那么nums[fast]可以放进nums[slow]中，并且slow++，记录结果的长度
• 当fast>=nums.size()的时候，结束循环，返回数组长度slow

复杂度分析：

• 时间复杂度O(n)
• 空间复杂度O(1)

代码实现：

class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if(n<=2){return n;}int slow = 2;int fast = 2;while(fast<n){if(nums[slow-2] != nums[fast]){nums[slow] = nums[fast];slow++;}fast++;}return slow;}
};

进一步可以优化掉快指针fast：

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

解题思路参考：
https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/solutions/702869/ju-yi-fan-er-ni-zhen-de-zhen-de-zhi-de-x-eicz/?envType=study-plan-v2&envId=top-interview-150