【代码随想录打卡】快慢指针-Toy模板网

这篇具有很好参考价值的文章主要介绍了【代码随想录打卡】快慢指针。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣链接：力扣

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路：考虑两个指针同时看这个nums数组，快指针跑的快一些（每一个循环都往后走一步），可以先去后面看看元素是什么。而慢指针走的慢一些（只有当快指针丢给他符合条件也就是nums[fast]!=val时才更新），这样慢指针接收到的数永远是fast筛选过符合条件的数。当fast走完一遍，slow指向的就是最后一个符合条件的数的下一个位置。

# 1.快慢指针同向，相当于快指针先跑到后面看看，把后面nums中不是val的值丢给慢指针，慢指针只负责接受不等于val的值
def removeElement(nums, val):
    slow = 0
    fast = 0
    while fast<len(nums):# 快指针看完一遍就该退出了，此时慢指针一定能使所有不为val的值都排在前面
        if nums[fast]!=val:# 快指针看完发现这个值不是val，就丢给慢指针
            nums[slow] = nums[fast]
            slow += 1
        fast += 1
    return slow

nums = [0,1,2,2,3,0,4,2]
val = 2
print(removeElement(nums, val))

如果删除指定val元素后剩余元素的顺序不要求和原来相等，那我们还可以用对撞指针，类似与快排用到的方法。文章来源地址https://www.toymoban.com/news/detail-524621.html

# 2.对撞指针，有点像快排，从左往右找到一个为val的值，再从右往左找一个不为val的值，把找到的两个数交换，这样所有不为val都会被换到前面
def removeElement(nums, val):
    left = 0
    right = len(nums)-1
    while left<=right:# left>right时可以退出了，必定已经交换完所有该交换的数了
        while nums[left] != val:
            left += 1
        while nums[right]==val:
            right -= 1
        if left<right:
            nums[left], nums[right] = nums[right], nums[left]
    return left + 1 if nums[left]!=val else left

nums = [0,1,2,2,3,0,4,2]
val = 2
print(removeElement(nums, val))

到了这里，关于【代码随想录打卡】快慢指针的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！