有没有高质量的网站都懂的,绍兴市建设局网站,舟山网站建设seo,做网站怎么找客户联系方式阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 让 index指向删除重复元素后数组的新长度#xff1b;让 st_idx 指向重复元素的起始位置#xff0c;而 i 指向重复元素的结束位置#xff0c;duplicate_num代表重复元素的个数#xff1b;一段重复元素结束后让 st_idx 指向重复元素的起始位置而 i 指向重复元素的结束位置duplicate_num代表重复元素的个数一段重复元素结束后这时候如果 st_idx index那么无需搬移数据只让 index 前进最多 2 个位置即可如上面上图到右图的过程所示如果 st_idx ! index我们需要从 st_idx 开始最多搬移 2 个数据到 index 位置如上面右图到左图的过程所示此时如果 i 指向最后一个元素那么直接将最后一个元素搬移到 index 位置直接返回如果 i 还没有到最后一个元素那么继续重复寻找下一段重复元素
3. 代码实现
class Solution:def removeDuplicates(self, nums: List[int]) - int:if len(nums) 3:return len(nums)index 0st_idx 0duplicate_num 1i 1target nums[0]while i len(nums):while i len(nums) and nums[i] target:duplicate_num 1i 1if st_idx ! index:for j in range(st_idx, st_idxmin(duplicate_num, 2)):nums[index] nums[st_idx]st_idx 1index 1else:index min(2, duplicate_num)if i len(nums) - 1:nums[index] nums[i]index 1return indexif i len(nums):st_idx itarget nums[i]duplicate_num 1i 1return index时间复杂度为 O ( n ) O(n) O(n)最多遍历 2 遍数组空间复杂度为 O ( 1 ) O(1) O(1)。
当然了上面的思路不容易理清比较简单的一个实现是利用快慢指针。一开始快慢指针都指向第 3 个元素如果 nums[fast] nums[slow-2]说明重复元素超过了 2 个只需要向前移动 fast 指针即可如果 nums[fast] ! nums[slow-2]那么把 fast 指针指向的元素移动到slow 指针二者都前进一步。最后slow指针指向的位置即为结果所求。
class Solution {
public:int removeDuplicates(vectorint nums) {if (nums.size() 3)return nums.size();int slow 2;int fast 2;while (fast nums.size()) {if (nums[fast] nums[slow-2]) {fast;} else {nums[slow] nums[fast];}}return slow;}
};
