刷题日记-Day1- Leedcode-704. 二分查找，27. 移除元素-Python实现

种花家的奋斗兔

发布于 2024-05-25 19:13:38

500

发布于 2024-05-25 19:13:38

文章被收录于专栏：NLP小白的学习历程NLP小白的学习历程

704 二分查找

链接：https://leetcode.cn/problems/binary-search/description/

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路：二分，关键点在于边界条件处理，此处使用left<=right ,原因是我们在区间【Left，Right】之间查找，left==right是有意义的，除此之外，判断分支后直接去掉mid，变为mid-1和mid+1,同样保证左闭右闭区间。

### Python实现
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        ## 注意是小于等于
        while left <= right:
            mid = (left + right) //2  ## 整除   
            if nums[mid] < target:
                left = mid+1
            elif nums[mid] > target:
                right = mid-1
            else:
                return mid
        return -1

27 移除元素

链接：https://leetcode.cn/problems/remove-element/description/

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路：双指针（快慢指针）设置左指针和右指针，最开始都在初始化的0位置，其中右指针在前’‘探路’'，遇到非目标值的，则将该值赋值给左指针位置，同时左右指针均右移动一位，如果遇到目标值，则右指针右移，左指针不动，最终结果是左指针左边的数字即为移除完所有目标值的数组。 Python实现：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l ,r = 0, 0
        for r, x in enumerate(nums):
            if x != val:
                nums[l] = x
                l += 1
        return l

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-24，如有侵权请联系 cloudcommunity@tencent.com 删除

指针