0%

[Leetcode]81. Search in Rotated Sorted Array II(C++)

题目描述

题目链接:81. Search in Rotated Sorted Array II

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

例子

例子 1

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

例子 2

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

Follow Up

This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the runtime complexity? How and why?

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums is guaranteed to be rotated at some pivot.
  • -10^4 <= target <= 10^4

解题思路

这道题和 [Leetcode]33. Search in Rotated Sorted Array(C++) 的区别在于数组可以有重复的数字。这里先把上一题的解答思路附上:

这里以当中间值 Mid > Target 为例,有以下情况:

图中两部分数组用颜色区分出来,Target 可能的位置用箭头标识出来,可以发现 Target 出现在 Mid 右侧的情况只有一种可能:LeftMid 为单调递增(排除中间情况),并且 Left 也比 Target 大(排除另外两种情况),此时收缩左边界,其余情况通通收缩右边界即可。对于 Mid < Target 也可以通过画图进行同样的分析,这里不赘述。

和这一题比较一下,可以发现当 Mid > Target 大部分情况是没有变的,但是对于左侧区间的单调性判断变了,在上一题中由于每个数字不重复,所以当 LeftMid 小(或等于,如果 Left = Right)时,我们可以从图上三种情况判断出左侧一定单调递增。但现在在有可能出现重复的情况下,我们必须考虑 Left = Mid 的情况,这种情况下左侧不一定具有单调性,有两种可能:

  • Left = Left + 1 = ... = Mid ( = ... = Right),此时左侧区间元素全部相等(并且有可能和右侧末尾部分元素相等),Target 在右侧区间
  • Mid = Mid + 1 = ... = Right = Left,此时右侧区间元素全部相等,并且和左侧前面部分元素相等, Target 在左侧区间

这种情况下我们没办法选择哪一边进行收缩,所以只能将 Left 往右移位重新搜索上。

Target > Mid 时思路类似,不再赘述。

代码如下:

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
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return true;
} else if (nums[mid] < target) {
if (nums[mid] == nums[right]) {
right--;
} else if (nums[right] < target && nums[mid] < nums[right]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] == nums[left]) {
left++;
} else if (nums[left] > target && nums[mid] > nums[left]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}

return false;
}
};
  • 时间复杂度: O(log n) -> O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 81.SearchInRotatedSortedArrayIi.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions