LeetCode 81. 搜索旋转排序数组 II — Python3 实现问题描述已知存在一个按非降序排列的整数数组nums数组中的值不必互不相同。在传递给函数之前nums在预先未知的某个下标k上进行了旋转使数组变为[nums[k], nums[k1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]。给你旋转后的数组nums和一个整数target如果nums中存在这个目标值target则返回True否则返回False。核心难点与 LC33无重复元素不同重复元素会导致无法判断哪一侧有序最坏情况退化为 O(n)。示例: [1, 0, 1, 1, 1], target 0nums[0] nums[2] nums[4] 1 → 无法判断左右哪边有序解法一二分查找 去重处理推荐【python】from typing import Listclass Solution:def search(self, nums: List[int], target: int) - bool:left, right 0, len(nums) - 1while left right: mid (left right) // 2 if nums[mid] target: return True # 关键当无法判断哪边有序时缩小边界 if nums[left] nums[mid] nums[right]: left 1 right - 1 # 左半部分有序 elif 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 False解法二简化版只处理左边重复【python】class Solution:def search(self, nums: List[int], target: int) - bool:left, right 0, len(nums) - 1while left right: mid (left right) // 2 if nums[mid] target: return True # 无法判断时只缩小左边界 if nums[left] nums[mid]: left 1 continue 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 False解法三先找旋转点 两次二分思路清晰【python】class Solution:def search(self, nums: List[int], target: int) - bool:n len(nums)if n 0:return False# 1. 找到旋转点最小值的下标 def find_rotate_index(): left, right 0, n - 1 while left right: mid (left right) // 2 if nums[mid] nums[right]: left mid 1 elif nums[mid] nums[right]: right mid else: # nums[mid] nums[right]无法判断 right - 1 return left rotate find_rotate_index() # 2. 确定在哪个区间搜索 if nums[rotate] target nums[n - 1]: left, right rotate, n - 1 else: left, right 0, rotate - 1 # 3. 标准二分查找 while left right: mid (left right) // 2 if nums[mid] target: return True elif nums[mid] target: left mid 1 else: right mid - 1 return False完整测试代码【python】def main():sol Solution()# 示例 1 nums1 [2, 5, 6, 0, 0, 1, 2] target1 0 print(f示例1: {sol.search(nums1, target1)}) # True # 示例 2 nums2 [2, 5, 6, 0, 0, 1, 2] target2 3 print(f示例2: {sol.search(nums2, target2)}) # False # 边界全重复 nums3 [1, 1, 1, 1, 1, 1, 1] target3 2 print(f边界1: {sol.search(nums3, target3)}) # False nums4 [1, 1, 1, 1, 1, 1, 1] target4 1 print(f边界2: {sol.search(nums4, target4)}) # True # 边界难判断的情况 nums5 [1, 0, 1, 1, 1] target5 0 print(f边界3: {sol.search(nums5, target5)}) # True # 空数组 nums6 [] target6 0 print(f边界4: {sol.search(nums6, target6)}) # False # 单元素 nums7 [1] target7 1 print(f边界5: {sol.search(nums7, target7)}) # Trueifname “main”:main()图解核心逻辑解法一nums [4,5,6,7,0,1,2], target 0第一轮: left0, right6, mid3 nums[3]7, nums[left]4, nums[right]2 nums[left] nums[mid] → 左半 [4,5,6,7] 有序 target0 不在 [4,7) → left mid1 4第二轮: left4, right6, mid5 nums[5]1, nums[left]0, nums[right]2 nums[left] nums[mid] → 左半 [0,1] 有序 target0 在 [0,1) → right mid-1 4第三轮: left4, right4, mid4 nums[4]0 target → ✅ True─────────────────────────────────────────nums [1,0,1,1,1], target 0 ← 重复元素难判断第一轮: left0, right4, mid2 nums[0]1, nums[2]1, nums[4]1 → 三者相等 left1, right-1 → left1, right3第二轮: left1, right3, mid2 nums[2]1, nums[left]0, nums[right]1 nums[left] nums[mid] → 左半 [0,1] 有序 target0 在 [0,1) → right mid-1 1第三轮: left1, right1, mid1 nums[1]0 target → ✅ True复杂度分析【表格】方法 平均时间 最坏时间 空间解法一二分去重 O(log n) O(n) O(1)解法二简化去重 O(log n) O(n) O(1)解法三找旋转点 O(log n) O(n) O(1)⚠️ 最坏情况数组全为相同元素且不等于 target退化为线性扫描 O(n)与 LC33 对比总结┌────────────┬──────────────────────┬──────────────────────┐│ │ LC33 无重复 │ LC81 有重复 │├────────────┼──────────────────────┼──────────────────────┤│ 判断有序 │ nums[left]nums[mid]│ 同左但需处理相等 ││ 额外处理 │ 不需要 │ left / right-- ││ 时间复杂度 │ O(log n) │ O(log n) ~ O(n) │└────────────┴──────────────────────┴──────────────────────┘