力扣hot100题解（python版63-68题）

63、搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的升序排列数组
-104 <= target <= 104

思路解答：

1、采用二分查找

使用两个指针left和right来表示当前搜索范围的左右边界。在每次迭代中，我们计算中间元素的索引mid，并将目标值与中间元素进行比较。

如果中间元素等于目标值，则直接返回中间元素的索引。
如果中间元素小于目标值，则更新left为mid + 1，继续在右半部分搜索。
如果中间元素大于目标值，则更新right为mid - 1，继续在左半部分搜索。

最终，当left > right时，表示搜索范围为空，此时left即为目标值应该插入的位置。

def searchInsert(nums: list[int], target: int) -> int:
    left, right = 0, 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 left

64、搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

思路解答：（同题21）

从矩阵的右上角开始，如果目标值等于当前位置的值，则返回True。
如果目标值大于当前位置的值，则目标值一定在当前位置的下方或左方，因为当前位置向左和向下都是递增的。
如果目标值小于当前位置的值，则目标值一定在当前位置的左上方，因为当前位置向上和向右都是递增的。
重复上述步骤，直到找到目标值或者搜索完整个矩阵。

def searchMatrix(matrix: list[list[int]], target: int) -> bool:

    if not matrix or not matrix[0]:

        return False

    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1

    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1
        else:
            col -= 1

    return False

65、在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

思路解答：

1、定义了两个辅助函数find_first和find_last来分别查找目标值的起始位置和结束位置

find_first函数找到第一个大于等于目标值的位置。
find_last函数找到最后一个小于等于目标值的位置。

2、如果起始位置小于等于结束位置，则返回起始位置和结束位置；否则返回[-1, -1]表示目标值不存在于数组中。

def searchRange(nums: list[int], target: int) -> list[int]:
    def find_first(nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (right + left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def find_last(nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (right + left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right

    start = find_first(nums, target)
    end = find_last(nums, target)

    if start <= end:
        return [start, end]
    else:
        return [-1, -1]

66、搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

思路解答：

初始化左指针 left 和右指针 right，分别指向数组的起始位置和结束位置。
在一个循环中，不断将中间位置 mid 计算为 (left + right) // 2。
如果 nums[mid] == target，表示找到了目标值，直接返回 mid。
接下来判断左半部分是否有序（即 nums[left] <= nums[mid]），如果是有序的，就根据目标值是否在有序部分内来更新左右指针；如果左半部分无序，则根据目标值是否在右半部分有序部分内来更新左右指针。
不断循环直到 left > right，表示没有找到目标值，返回 -1。

def search(nums: list[int], target: int) -> int:

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:  # 左半部分有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半部分有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

67、寻找旋转排序数组中的最小值

已知一个长度为 n的数组，预先按照升序排列，经由 1到 n 次旋转后，得到输入数组。例如，原数组

nums = [0,1,2,4,5,6,7]

在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

思路解答：

初始化左指针 left 指向数组开头，右指针 right 指向数组末尾。
在每一步中，计算中间元素的索引 mid = (right + left) // 2。
检查中间元素 nums[mid] 与最右边元素 nums[right] 的大小关系：
- 如果 nums[mid] < nums[right]，说明右半部分是有序的，最小元素可能在左半部分，因此将 right 移动到 mid。
- 如果 nums[mid] >= nums[right]，说明右半部分是无序的，最小元素一定在右半部分，因此将 left 移动到 mid + 1。
重复步骤 2 和步骤 3，直到 left 和 right 相遇，此时找到了最小元素。

def findMin(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (right + left) // 2

        if nums[mid] < nums[right]:  # 右半部分有序，最小值在左半部分或者就是当前位置
            right = mid
        else:  # 右半部分无序，最小值在右半部分
            left = mid + 1

    return nums[left]

68、寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

思路解答：

如果第一个数组的长度大于第二个数组的长度，则交换两个数组。
初始化一个极大值变量infinty，并分别获取两个数组的长度。
初始化left和right分别指向第一个数组的起始和结束位置，median1和median2初始化为0。
在left小于等于right的循环内，计算i和j，其中i表示第一个数组的分割点，j表示第二个数组的分割点。
根据i和j，获取四个数值nums_im1、nums_i、nums_jm1、nums_j，分别表示两个数组中的前一部分的最大值和后一部分的最小值。
如果nums_im1小于等于nums_j，则更新median1和median2的值，并将left更新为i + 1，否则将right更新为i - 1。
循环结束后，根据两个数组的总长度是奇数还是偶数，返回中位数的值。

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:

    if len(nums1) > len(nums2):
        return findMedianSortedArrays(nums2, nums1)

    infinty = 2 ** 40
    m, n = len(nums1), len(nums2)
    left, right = 0, m
    # median1：前一部分的最大值
    # median2：后一部分的最小值
    median1, median2 = 0, 0

    while left <= right:
        # 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
        # // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
        i = (left + right) // 2
        j = (m + n + 1) // 2 - i

        # nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
        nums_im1 = (-infinty if i == 0 else nums1[i - 1])
        nums_i = (infinty if i == m else nums1[i])
        nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
        nums_j = (infinty if j == n else nums2[j])

        if nums_im1 <= nums_j:
            median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
            left = i + 1
        else:
            right = i - 1

    return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1