Algorithm-RemoveElem
date
Oct 23, 2023
slug
algorithm-removeElem
status
Published
tags
algorithm
type
Post
https://twitter.com/tangdahe
summary
remove elem
移除元素
- 快慢指针进行求解
- 快指针可以理解成在旧数组中找非目标元素，然后赋值给慢指针指向的新数组，虽然都指向一个数组
- 关于二分法和移除元素的共性思考这两题之间有点类似的，他们都是在不断缩小 left 和 right 之间的距离，每次需要判断的都是 left 和 right 之间的数是否满足特定条件。对于「移除元素」这个写法本质上还可以理解为，我们拿 right 的元素也就是右边的元素，去填补 left 元素也就是左边的元素的坑，坑就是 left 从左到右遍历过程中遇到的需要删除的数，因为题目最后说超过数组长度的右边的数可以不用理，所以其实我们的视角是以 left 为主，这样想可能更直观一点。用填补的思想的话可能会修改元素相对位置，这个也是题目所允许的。
- fast < nums.size() 和 fast <= nums.size()-1 没什么区别，那为什么第二个会在空数组时报数组越界的错误？vector的size()函数返回值是无符号整数，空数组时返回了0，再减个一会溢出
27 移除元素
双指针（双向）思路：有点类似于快排
- 左右指针遍历
- 左指针寻找是目标值的 idx
- 右指针寻找不是目标值的 idx
- swap，左右指针遍历时需要保证 左指针永远小于等于右指针
双指针法（快慢指针法）
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
26 删除有序数组中的重复项
思路：快慢指针
- 和上述 27 不一样的地方为该数组现在是非严格递增排列的，就是说相同的 val 是在一起的，因此不能使用双向指针进行遍历。同时数组虽然保证有序，但是不能使用二分进行（非查找操作），只能采用快慢指针。
- 快指针寻找值不等于慢指针，更新慢指针的下一位，然后慢指针增加1即可
283 移动零
给定一个数组
nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
思路： 和上述 26 的解法一样，之所以不能使用双向指针，是这里要保证非零值依旧相对有序，快慢指针要 swap 更新数据，零值即跳过
844 比较含有退格的字符串
思路：进行字符串复制，空间复杂度较高，为O(n+m)
思路：双指针，依旧是快慢指针，不能使用双向指针。由于 # 号只会消除左边的一个字符，所以对右边的字符无影响，所以我们选择从后往前遍历 S，T 字符串。空间复杂度为 O(1)
思路解析：
- 准备两个指针 i,j 分别指向 S, T 的末位字符，在准备两个变量 skipS, skipT 来分别存放 S，T 字符串中的 # 数量
- 从后往前遍历 S
- 如果当前字符是 #， skip 自增
- 如果当前字符不是 #，skip 自减
- 如果当前字符不是 #，且 skip = 0，表示当前字符不能被消除，跳出字符串循环
- 从后往前遍历 T，操作同 2
- 比较 s[i] == t[j]，如果相同则继续 2，3，反之不相同则结束逻辑，返回 false
- 遍历结束返回 true
977 有序数组的平方
进阶要求，时间复杂度为 O(n)
思路：双指针
- 使用二分遍历出第一个 ≥0 的 idx，然后分为左右两个子数组，依次向左和向右遍历，每次比较左右 idx 的平方值，小的升序进入新的数组
- 使用双向指针，直接从数组最左和最右进行遍历，每次比较左右 idx 的平方值，大的逆序进入新的数组