[LeetCode]81. Search in Rotated Sorted Array II

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
2
3
4
5
6
7
8
Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
// nums[mid] <= nums[right]: 不能保证[mid, right]为递增序列
//eg: [1,1,3,1]: 细分分成nums[mid] < nums[right];
// nums[mid] == nums[right]: 不能确定,因为mid肯定不是,
// 那么right对应位置也不是, 跳过right

while (left <= right){
int mid = left + (right - left)/2;

if (nums[mid] == target)
return true;
else if (nums[mid] < nums[right]){
if (nums[mid] < target && nums[right] >= target)
left = mid + 1;
else
right = mid - 1;
}
else if (nums[mid] > nums[right]){
if (nums[left] <= target && nums[mid] > target)
right = mid -1;
else
left = mid + 1;
}
else
right--;
}
return false;
}
};
您的支持就是我更新的最大动力!谢谢!