[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索 II

时间:2023-03-08 23:43:02
[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索 II

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 题目汇总