网站建设内容模板,烟台网站建设推广,合肥房产备案查询官网,企业制作网站公司1 删除有序数组中的重复项
1.1 题目描述 给你一个 升序排列 的数组 nums #xff0c;请你 原地 删除重复出现的元素#xff0c;使每个元素 只出现一次#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度#xff0c…1 删除有序数组中的重复项
1.1 题目描述 给你一个 升序排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度所以必须将结果放在数组nums的第一部分。更规范地说如果在删除重复项之后有 k 个元素那么 nums 的前 k 个元素应该保存最终结果。 将最终结果插入 nums 的前 k 个位置后返回 k 。 不要使用额外的空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 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.2 思路分析 已知数组 nums 是有序的而且我们只能在原地修改 nums 数组不能创建新的数组空间来存储删除重复出现的元素后的结果。我们需要一边遍历数组查找相同元素一边在对比发现不同元素时修改数组元素那么我们可以考虑双指针法的快慢指针了定义 p 和 q 作为指针初始化时指针 p 指向数组的起始位置nums[0]指针 q 指向指针 p 的后一个位置nums[1]。随着指针 q 不断向后移动将指针 q 指向的元素与指 p 指向的元素进行比较
如果nums[q] ≠ nums[p]那么nums[p 1] nums[q]如果nums[q] nums[p]那么指针q继续向后查找
图示
1.3 代码实现
class Solution:def removeDuplicates(self, nums: List[int]) - int:p, q 0, 1while q len(nums):if nums[q] ! nums[p]:p 1nums[p] nums[q]q 1return p 1复杂度分析时间复杂度O(n)O(n)O(n)。 空间复杂度O(1)O(1)O(1)。 进一步优化 考虑如下数组 此时数组中没有重复元素按照上面的方法每次比较时 nums[p] 都不等于 nums[q]因此就会将 q 指向的元素原地复制一遍这个操作其实是不必要的。 因此我们可以添加一个小判断当 q - p 1 时才进行复制。
class Solution:def removeDuplicates(self, nums: List[int]) - int:p, q 0, 1while q len(nums):if nums[q] ! nums[p]:if q - p 1:nums[p1] nums[q]p 1q 1return p 12 删除有序数组中的重复项 II 给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。 不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1 输入nums [1,1,1,2,2,3] 输出5, nums [1,1,2,2,3] 解释函数应返回新长度 length 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。 示例 2 输入nums [0,0,1,1,1,1,2,3,3] 输出7, nums [0,0,1,1,2,3,3] 解释函数应返回新长度 length 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。 思路和上面的类似改变的地方是初始化时指针 p 指向数组的起始位置nums[1]指针 q 指向指针 p 的后一个位置nums[2]。随着指针 q 不断向后移动将指针 q 指向的元素与指 p 指向的元素进行比较
如果nums[q] ≠ nums[p-1]那么nums[p 1] nums[q]如果nums[q] nums[p]那么指针q继续向后查找
python
class Solution:def removeDuplicates(self, nums: List[int]) - int:p, q 1, 2while q len(nums):if nums[q] ! nums[p-1]:p 1nums[p] nums[q]q 1return p 1通用解法 为了让解法更具有一般性我们将原问题的「最多保留 1 位」修改为「最多保留 k 位」。 对于此类问题我们应该进行如下考虑
由于是保留 k 个相同数字对于前 k 个数字我们可以直接保留。对于后面的任意数字能够保留的前提是与当前写入的位置前面的第 k 个元素进行比较不相同则保留。 此时初始化时指针 p 指向数组的起始位置nums[k-1]指针 q 指向指针 p 的后一个位置nums[k]。随着指针 q 不断向后移动将指针 q 指向的元素与指 p 指向的元素进行比较
如果nums[q] ≠ nums[p-k1]那么nums[p 1] nums[q]如果nums[q] nums[p]那么指针q继续向后查找
