初学python的我开始Leetcode题11-2

发布于：2025-07-05 ⋅ 阅读:(21) ⋅ 点赞:(0)

提示：100道LeetCode热题-11-1主要是二分查找相关，包括三题：搜索旋转排序数组、寻找旋转排序数组中的最小值、寻找两个正序数组的中位数。由于初学，所以我的代码部分仅供参考。

前言

上次的三道二分查找题较为基础，主要是回顾和简单运用二分查找这一常见方法，这次的稍加了难度，大家一起看看吧~o(*￣▽￣*)ブ

提示：以下是本篇文章正文内容，下面结果代码仅供参考

题目1：搜索旋转排序数组

1.题目要求：

题目如下：

整数数组 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

  • -10^{4} <= nums[i] <= 10^{4}

  • nums 中的每个值都 独一无二

  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转

  • -10^{4} <= target <= 10^{4}

代码框架已经提供如下：

class Solution(object):

    def search(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: int

        """

2.结果代码：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: 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

说明：

本题还算基础，为下一题做准备。由于每次都将搜索范围缩小一半，时间复杂度为 O(log n)，满足题目要求。

  1. ​​初始化指针​​：left 和 right 分别指向数组的起始和结束位置。
  2. ​​二分查找​​：
    • 计算 mid 位置。
    • 如果 nums[mid] 等于 target，直接返回 mid。
    • 判断左半部分是否有序：
      • 如果 nums[left] <= nums[mid]，说明左半部分有序。
        • 如果 target 在 [nums[left], nums[mid]) 范围内，则在左半部分继续查找（调整 right）。
        • 否则在右半部分查找（调整 left）。
      • 如果右半部分有序：
        • 如果 target 在 (nums[mid], nums[right]] 范围内，则在右半部分继续查找（调整 left）。
        • 否则在左半部分查找（调整 right）。
  3. ​​未找到目标​​：如果循环结束仍未找到 target，返回 -1。

题目2：寻找旋转排序数组中的最小值

1.题目要求：

题目如下：

已知一个长度为 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] ，旋转 4 次得到输入数组。

示例 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 次旋转

代码框架已经提供如下：

class Solution(object):

    def findMin(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

2.结果代码：

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = (left + right) // 2
            
            if nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1
        
        return nums[left]

说明：

我们需要在一个旋转后的有序数组中查找最小值。旋转后的数组不再是全局有序的，但可以被分成两个有序的子数组。例如，[4,5,6,7,0,1,2] 是由 [0,1,2,4,5,6,7] 旋转得到的，分为 [4,5,6,7] 和 [0,1,2] 两个有序部分，最小值 0 位于两个子数组的交界处。

由于数组是部分有序的，我们可以利用二分查找的思想，通过比较中间元素与右边界元素的大小关系来判断最小值的位置。具体步骤如下：

  1. ​​初始化指针​​：设置 left 和 right 分别指向数组的起始和结束位置。
  2. ​​二分查找​​：
    • 计算中间位置 mid。
    • 如果 nums[mid] < nums[right]，说明最小值在左半部分或就是 mid 本身，因此更新 right = mid。
    • 否则，最小值在右半部分，更新 left = mid + 1。
  3. ​​终止条件​​：当 left == right 时，nums[left] 即为最小值。

题目3：寻找两个正序数组的中位数

1.题目要求：

题目如下：

给定两个大小分别为 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

  • -10^{6} <= nums1[i], nums2[i] <= 10^{6}

代码框架已经提供如下：

class Solution(object):

    def findMedianSortedArrays(self, nums1, nums2):

        """

        :type nums1: List[int]

        :type nums2: List[int]

        :rtype: float

        """

2.结果代码：

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        total_len = m + n
        half_len = (total_len + 1) // 2
        
        low, high = 0, m
        while low <= high:
            i = (low + high) // 2
            j = half_len - i
            
            max_left1 = nums1[i-1] if i > 0 else float('-inf')
            min_right1 = nums1[i] if i < m else float('inf')
            max_left2 = nums2[j-1] if j > 0 else float('-inf')
            min_right2 = nums2[j] if j < n else float('inf')
            
            if max_left1 <= min_right2 and max_left2 <= min_right1:
                if total_len % 2 == 1:
                    return max(max_left1, max_left2)
                else:
                    return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
            elif max_left1 > min_right2:
                high = i - 1
            else:
                low = i + 1
        return 0.0

问题分析：

我们需要在两个有序数组 nums1 和 nums2 中找到合并后的中位数。中位数的定义是将数组分成两部分，左半部分的所有元素小于等于右半部分的所有元素。如果合并后的数组长度为奇数，中位数是中间的那个数；如果长度为偶数，中位数是中间两个数的平均值。题目要求算法的时间复杂度为 O(log(m+n))，这意味着我们需要使用二分查找的思想来解决这个问题。

解决思路：

为了满足时间复杂度要求，我们可以利用二分查找的思想，通过每次排除一半的元素来缩小搜索范围。具体步骤如下：

  1. ​​确定中位数的位置​​：根据合并后数组的总长度 total_length = m + n，如果 total_length 是奇数，中位数是第 k = (total_length + 1) // 2 小的元素；如果是偶数，中位数是第 k1 = total_length // 2 和第 k2 = k1 + 1 小的元素的平均值。
  2. ​​二分查找第 k 小的元素​​：
    • 比较 nums1 和 nums2 中第 k//2 小的元素（如果数组长度不足 k//2，则取最后一个元素）。
    • 如果 nums1 的第 k//2 小的元素小于 nums2 的第 k//2 小的元素，说明 nums1 的前 k//2 个元素不可能是第 k 小的元素，可以排除这部分元素，并更新 k 为 k - k//2。
    • 反之，排除 nums2 的前 k//2 个元素。
    • 重复上述过程，直到 k 为 1 或其中一个数组被完全排除。
  3. ​​处理边界条件​​：
    • 如果一个数组为空，直接返回另一个数组的第 k 小的元素。
    • 如果 k 为 1，返回两个数组当前指针位置的较小值。

优化点说明：

  1. ​​减少冗余计算​​：

    • 直接交换 nums1 和 nums2，确保 nums1 是较短的数组，减少二分查找的范围。
    • 使用 half_len 直接计算中位数的位置，避免重复计算。

  2. ​​提前终止​​：

    • 在二分查找中，一旦找到满足条件的分割点，立即返回结果，减少不必要的迭代。

  3. ​​边界处理优化​​：

    • 使用 float('-inf') 和 float('inf') 处理边界情况，避免复杂的条件判断。

总结

针对二分查找的三种题型进行了学习，了解了部分有关二分查找与python的相关知识，大家加油！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布