Problem
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
1 | Example 1: |
Follow up:
- This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
- Would this affect the run-time complexity? How and why?
这个题作为33题Search in Rotated Sorted Array的扩展题,或者说变形题. 由原来不存在重复元素的数组,变为存在重复元素的颠倒数组. 其他条件类似, 给定target在数组中查找这个target, 存在,返回true,不存在返回false.
Solution
Analysis
由于重复元素的存在, nums[mid]和nums[right]之间就并不仅仅是大下关系了, 两者有可能相等. 但是判断条件nums[mid] < nums[right]如果满足,那么这个子区间一定是有序的, 此外, 如果两者相等, 因为之前已经判断过nums[mid]和target之间的对等关系, 所以我们可以确定nums[right]!=target. 所以,可以变换right的范围,让right自减. 其他情况就类似.
具体实现,看代码.
Code
1 | class Solution { |