台州网站优化方案,网站开发和程序开发,企业一般用什么邮箱?,网站建设初步规划书【刷题笔记】数组-双指针||覆盖||重复元素 目录 移除元素删除有序数组中的重复项删除有序数组中的重复项 II分析 移除元素
https://leetcode.cn/problems/remove-element/
给你一个数组 nums 和一个值 val#xff0c;你需要 原地 移除所有数值等于 val 的元素#xff0c;并…【刷题笔记】数组-双指针||覆盖||重复元素 目录 移除元素删除有序数组中的重复项删除有序数组中的重复项 II分析 移除元素
https://leetcode.cn/problems/remove-element/
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
class Solution(object):def removeElement(self, nums, val):if len(nums) 0:return 0slow, fast 0, 0while fast len(nums):if nums[fast] ! val:nums[slow] nums[fast]slow slow 1fast fast 1return slow删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。
class Solution(object):def removeDuplicates(self, nums)::type nums: List[int]:rtype: intslow, fast 1, 1while fast len(nums):if nums[slow - 1] ! nums[fast]:nums[slow] nums[fast]slow slow 1fast fast 1return slow删除有序数组中的重复项 II
https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/
给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。
不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
class Solution {public int removeDuplicates(int[] nums) {if (nums.length 2) return nums.length;int slow 2, fast 2;while (fast nums.length) {if (nums[slow - 2] ! nums[fast])nums[slow] nums[fast];fast;}return slow;}
}分析
这一类题目在数组中原地修改这种题目经常利用后面的元素将前面的元素覆盖。这涉及到两个指针一个slow一个fast。slow代表我们当前的索引该索引位置有两个可能操作保留、覆盖。fast表示真正的遍历索引判断该元素是否符合题目要求如果符合则利用该元素覆盖slow位置。
比如删除有序数组中的重复项 II题目中我们首先设置slow0fast0。然后设置大体框架
slow, fast 0, 0
while (fast len(nums)): ...我们看到fast是真实的遍历指针所以判断遍历的框架也是利用fast。
接下来判断fast是否满足条件nums[fast] ! val如果满足条件则将该元素在slow位置上覆盖。
而对于删除多个重复项这个问题我们依然满足这个框架
slow, fast
while fast len(nums): ...在做算法题的时候我们需要用一般性思维即不要一上来就考虑初始条件或者边界条件而是要从一般情况下考虑问题。
假设我们已经到算法中间的某一步此时我们认为slow之前的元素都已经满足要求那么fast什么时候可以覆盖重写slow位置上的元素呢
如上图假设 v m v_m vm可以放在slow的位置那么 v m v_m vm不应该和 v k − 2 v_{k-2} vk−2相等。因为什么再次强调我们应该具备一般思维当我们的指针走到slow的时候slow之前的元素完全满足每个元素最多有两个也就是说最坏的情况就是 v k − 2 v k − 1 v m v_{k-2}v_{k-1}v_m vk−2vk−1vm即
nums[slow-2] nums[slow-1] and
nums[slow-1] nums[fast]❓但是我们发现在代码中的判定条件只有nums[slow-2]和nums[fast]因为数组是有序的如果nums[slow-2] nums[fast]则证明nums[slow-1]也等于nums[fast]。如果nums[slow-2] ! nums[fast]则有两种情况nums[slow-1]等于或者不等于nums[fast]而这两种情况都是满足要求的。
所以我们补全代码
while fast len(nums): if nums[slow - 2] ! nums[fast]: nums[slow] nums[fast]slow slow 1fast fast 1当你刚写下nums[slow - 2]的时候就有疑问了要是初始设置slow0那这一步就该报错了。这说明我们初始的时候应该设置slow和fast都为2因为nums的前两个元素一定满足要求判断过程从第三个元素开始。
按照题目要求最后我们要返回新数组的长度我们看更新过程
nums[slow] nums[fast]
slow slow 1首先slow被更新然后slow前进一步那么当最后一个元素被填入slow之后slow加一即比最后一个合理元素的索引大1也就是长度。最后直接返回slow。
class Solution(object):def removeDuplicates(self, nums)::type nums: List[int]:rtype: intif len(nums) 2:return len(nums)slow, fast 2, 2while fast len(nums):if nums[slow - 2] ! nums[fast]:nums[slow] nums[fast]slow slow 1fast fast 1return slow
