[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索 II
2023-09-27 14:28:37 时间
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
33. Search in Rotated Sorted Array 的拓展,数组中允许出现重复数字,这个也会影响我们选择哪半边继续搜索,之前判断左右部分是否有序的方法就失效了,因为可能有这种58555情况,虽然起点小于等于中间,但不代表右边就不是有序的,因为中点也小于等于终点,所有右边也是有序的。所以,如果遇到这种中点和两边相同的情况,我们两边都要搜索。
Java:
public class Solution { public boolean search(int[] nums, int target) { return helper(nums, 0, nums.length - 1, target); } public boolean helper(int[] nums, int min, int max, int target){ int mid = min + (max - min) / 2; // 不符合min <= max则返回假 if(min > max){ return false; } if(nums[mid] == target){ return true; } boolean left = false, right = false; // 如果左边是有序的 if(nums[min] <= nums[mid]){ // 看目标是否在左边有序数列中 if(nums[min] <= target && target < nums[mid]){ left = helper(nums, min, mid - 1, target); } else { left = helper(nums, mid + 1, max, target); } } // 如果右边也是有序的 if(nums[mid] <= nums[max]){ // 看目标是否在右边有序数列中 if(nums[mid] < target && target <= nums[max]){ right = helper(nums, mid + 1, max, target); } else { right = helper(nums, min, mid - 1, target); } } // 左右两边有一个包含目标就返回真 return left || right; } }
Python:
class Solution(object): def search(self, nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) / 2 if nums[mid] == target: return True elif nums[mid] == nums[left]: left += 1 elif (nums[mid] > nums[left] and nums[left] <= target < nums[mid]) or \ (nums[mid] < nums[left] and not (nums[mid] < target <= nums[right])): right = mid - 1 else: left = mid + 1 return False
类似题目:
[LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索
All LeetCode Questions List 题目汇总
相关文章
- 通过 LeetCode 周赛学习二分查找算法
- Leetcode: Sum Root to Leaf Numbers
- Leetcode: Maximum Subarray
- Leetcode: Reverse Words in a String
- Leetcode: Subsets
- LeetCode高频题33. 搜索旋转排序数组
- JS leetcode 寻找旋转排序数组中的最小值 题解分析,你不得不了解的二分法
- [算法]LeetCode 152:乘积最大子序列
- LeetCode题解——700.二叉树搜索树中的搜索
- 198、【动态规划】leetcode ——983. 最低票价:记忆化搜索(C++版本)
- 149、【动态规划】leetcode ——343. 整数拆分(C++版本)
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- LeetCode——Convert Sorted Array to Binary Search Tree
- 【leetcode】:109. 有序链表转换二叉搜索树
- 【leetcode】108:将有序数组转化为二叉搜索树
- [LeetCode] 1268. Search Suggestions System 搜索推荐系统
- [LeetCode] 1008. Construct Binary Search Tree from Preorder Traversal 从先序遍历重建二叉搜索树
- [LeetCode] 776. Split BST 分割二叉搜索树
- [LeetCode] Russian Doll Envelopes 俄罗斯娃娃信封
- [LeetCode] 255. Verify Preorder Sequence in Binary Search Tree 验证二叉搜索树的先序序列
- [LeetCode] 247. Strobogrammatic Number II 对称数之二
- [LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二
- [LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树
- [LeetCode] Binary Search Tree Iterator 二叉搜索树迭代器
- leetcode 680. Valid Palindrome II 验证回文字符串 Ⅱ
- 莫名其妙的越界错误原因之条件判断顺序——基于LeetCode 99题,恢复二叉搜索树
- leetcode算法235.二叉搜索树的最近公共祖先