沈阳网站建设咨询,网站规划的任务,建立网站难吗,网站建设-部署与发布题目描述
给你一个有序数组 nums #xff0c;请你 原地 删除重复出现的元素#xff0c;使得出现次数超过两次的元素只出现两次 #xff0c;返回删除后数组的新长度。
不要使用额外的数组空间#xff0c;你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。…题目描述
给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。
不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
题目解法
使用了快慢指针
快指针 (fast)遍历整个数组。慢指针 (slow)指向下一个有效元素即允许保留的元素应该存放的位置其最终值就是新数组的长度。
核心逻辑对于当前快指针 fast指向的元素检查它是否与 nums[slow - 2]相同。如果不同说明这个元素例如 nums[fast]的出现次数还没有达到两次可以保留于是将其复制到 slow的位置然后 slow前进一步。
这里有个问题是为什么nums[fast]和nums[slow - 2]比较呢
慢指针 slow不仅指向下一个待插入位置其前方的区域[0, slow-1]已经是处理好的、满足每个元素最多出现两次要求的“新数组”。nums[slow - 2]代表了“新数组”中当前正在检查的元素的“上一次可能重复”的位置。
更详细的说明下由于数组有序如果 nums[fast]当前遍历到的元素与 nums[slow - 2]新数组中的前一个相同元素相等意味着如果放入 nums[slow]就会导致 nums[slow - 2], nums[slow - 1]和 nums[slow]三个连续相同的元素这违反了“最多出现两次”的规则。因此只有不相等时才能放入。
class Solution {public int removeDuplicates(int[] nums) {if (nums.length 2) {return nums.length;}int slow 2;for (int fast 2; fast nums.length; fast) {if (nums[fast] ! nums[slow - 2]) {nums[slow] nums[fast];slow;}}return slow;}
}
