1
27. 移除元素
source link: https://sexywp.com/27-remove-element.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
简述一下题目的意思：给你一个数组 nums 和一个值 val ，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
这个题目的全文太长了，我就不全部挪过来了，就是提示一下这个意思就行了。具体可以去 LC 上查看。
这个题目感觉和 26 题极其相似，我第一个想到的就是“双指针”，第一个指针标记筛后的数组的末位，第二个指针指向筛前数组的开头。然后，两个指针的初始化都在 0，我们这么考虑问题，从筛选前的数字的第一个元素开始，如果这个元素没命中 target 就拷贝到筛选后数组的最后一位，如果命中了，就跳过看第二个元素。
因为筛选用的那个指针移动速度大于等于筛选后的那个指针，所以这个算法会没有重复和遗漏地结束。写出来是：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, j = 0, 0
while j < len(nums):
if nums[j] != val:
nums[i] = nums[j]
i += 1
j += 1
return i
也是非常短的。写完我看了下答案，原来还有优化的空间，就是我这个算法，拷贝的次数比较多，因为如果整个数组都没有命中的数字，那么每个数字都要被原地赋值一次，确实如此。
如果我们不纠结元素的顺序，可以使用交换法，还是双指针，一个初始化在筛后数字的开头，一个指向筛前数组的末位，就是倒着筛，筛到就交换。这样就极大减少了赋值的次数，提高了效率。很有意思。
知识点：无新的知识点。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK