初學python的我開始Leetcode題11-2

提示：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
- <= nums[i] <=
nums?中的每個值都?獨一無二
題目數據保證?nums?在預先未知的某個下標上進行了旋轉
- <= target <=

代碼框架已經提供如下：

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) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return mid# 左半部分有序if nums[left] <= nums[mid]:if nums[left] <= target < nums[mid]:right = mid - 1else:left = mid + 1# 右半部分有序else:if nums[mid] < target <= nums[right]:left = mid + 1else:right = mid - 1return -1

說明：

本題還算基礎，為下一題做準備。由于每次都將搜索范圍縮小一半，時間復雜度為?O(log n)，滿足題目要求。

??初始化指針??：left?和?right?分別指向數組的起始和結束位置。
??二分查找??：
- 計算?mid?位置。
- 如果?nums[mid]?等于?target，直接返回?mid。
- 判斷左半部分是否有序：
  - 如果?nums[left] <= nums[mid]，說明左半部分有序。
    - 如果?target?在?[nums[left], nums[mid])?范圍內，則在左半部分繼續查找（調整?right）。
    - 否則在右半部分查找（調整?left）。
  - 如果右半部分有序：
    - 如果?target?在?(nums[mid], nums[right]]?范圍內，則在右半部分繼續查找（調整?left）。
    - 否則在左半部分查找（調整?right）。
??未找到目標??：如果循環結束仍未找到?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) - 1while left < right:mid = (left + right) // 2if nums[mid] < nums[right]:right = midelse:left = mid + 1return nums[left]

說明：

我們需要在一個旋轉后的有序數組中查找最小值。旋轉后的數組不再是全局有序的，但可以被分成兩個有序的子數組。例如，[4,5,6,7,0,1,2]?是由?[0,1,2,4,5,6,7]?旋轉得到的，分為?[4,5,6,7]?和?[0,1,2]?兩個有序部分，最小值?0?位于兩個子數組的交界處。

由于數組是部分有序的，我們可以利用二分查找的思想，通過比較中間元素與右邊界元素的大小關系來判斷最小值的位置。具體步驟如下：

??初始化指針??：設置?left?和?right?分別指向數組的起始和結束位置。
??二分查找??：
- 計算中間位置?mid。
- 如果?nums[mid] < nums[right]，說明最小值在左半部分或就是?mid?本身，因此更新?right = mid。
- 否則，最小值在右半部分，更新?left = mid + 1。
??終止條件??：當?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
- <= nums1[i], nums2[i] <=?

代碼框架已經提供如下：

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, nums1m, n = len(nums1), len(nums2)total_len = m + nhalf_len = (total_len + 1) // 2low, high = 0, mwhile low <= high:i = (low + high) // 2j = half_len - imax_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.0elif max_left1 > min_right2:high = i - 1else:low = i + 1return 0.0

問題分析：

我們需要在兩個有序數組?nums1?和?nums2?中找到合并后的中位數。中位數的定義是將數組分成兩部分，左半部分的所有元素小于等于右半部分的所有元素。如果合并后的數組長度為奇數，中位數是中間的那個數；如果長度為偶數，中位數是中間兩個數的平均值。題目要求算法的時間復雜度為?O(log(m+n))，這意味著我們需要使用二分查找的思想來解決這個問題。

解決思路：

為了滿足時間復雜度要求，我們可以利用二分查找的思想，通過每次排除一半的元素來縮小搜索范圍。具體步驟如下：

??確定中位數的位置??：根據合并后數組的總長度?total_length = m + n，如果?total_length?是奇數，中位數是第?k = (total_length + 1) // 2?小的元素；如果是偶數，中位數是第?k1 = total_length // 2?和第?k2 = k1 + 1?小的元素的平均值。
??二分查找第 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 或其中一個數組被完全排除。
??處理邊界條件??：
- 如果一個數組為空，直接返回另一個數組的第?k?小的元素。
- 如果?k?為 1，返回兩個數組當前指針位置的較小值。

優化點說明：

??減少冗余計算??：
- 直接交換?nums1?和?nums2，確保?nums1?是較短的數組，減少二分查找的范圍。
- 使用?half_len?直接計算中位數的位置，避免重復計算。
??提前終止??：
- 在二分查找中，一旦找到滿足條件的分割點，立即返回結果，減少不必要的迭代。
??邊界處理優化??：
- 使用?float('-inf')?和?float('inf')?處理邊界情況，避免復雜的條件判斷。