题目描述

题目链接：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 右侧的情况只有一种可能：Left 到 Mid 为单调递增（排除中间情况），并且 Left 也比 Target 大（排除另外两种情况），此时收缩左边界，其余情况通通收缩右边界即可。对于 Mid < Target 也可以通过画图进行同样的分析，这里不赘述。

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

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

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

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

代码如下：

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