【随想录day1】LeetCode704二分查找| LeetCode27移除元素

三法师 / 2024-09-13 / 原文

LeetCode704二分查找

1、题目：

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

2、代码

2.1 Python版

一些注意点：

c++代码中int相加防止越界，python中则用整数除
区间的问题
区间指的是target在二分查找过程中的下表搜索范围，一般采用左闭右闭或者左闭右开区间。

左闭右闭

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0 
        right = len(nums)- 1
        while left <= right:
            #这里整数相加要注意溢出的问题,python不需要考虑，但是要用整数除法。否则会以浮点数报错。
            middle = (left + right) // 2

            if nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            elif nums[middle] == target:
                return middle
        return -1

左闭右开

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)
        while left < right:
            #这里整数相加要注意溢出的问题,python不需要考虑，但是要用整数除法。否则会以浮点数报错。
            middle = (left + right) // 2

            if nums[middle] > target:
                right = middle
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1

2.2 C++版（todo）

3、总结

1.left和right的初始化
2.while循环中的left、right判定
3.target比较过程中的left和right下标调整

LeetCode27移除元素

1、题目：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

2、代码

2.1 Python版

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast = 0
        slow = 0
        size = len(nums)
        while fast < size:
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow +=1
            fast +=1
        return slow