LeetCode: 81. Search in Rotated Sorted Array 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.

题目大意：将 LeetCode 33. Search in Rotated Sorted Array 题目要求的“没有重复元素”(no duplicate exists in the array) 改为了 “有重复元素”(The array may contain duplicates.)。 即： 将一个递增序列的前几个项移到最后, 然后让我们搜索指定的项(target)。数组中有重复的数字出现。

解题思路

一般情况主要分析过程如 LeetCode: 33. Search in Rotated Sorted Array 所写。

需要注意的是，由于数组中有重复的元素，所以当 nums[left] == nums[mid] && nums[mid] == nums[right] 时， target 可能在 [left, mid) 区间，也可能在 [mid, right) 区间，如图：

• nums[left] == nums[mid] && nums[mid] == nums[right], target 在区间 [left, mid)：
  

• nums[left] == nums[mid] && nums[mid] == nums[right], target 在区间 [mid, right)：
  

AC 代码(根据 LeetCode: 33. Search in Rotated Sorted Array 修改)

class Solution {
public:
    int s(vector<int>& nums, int left, int right, int target)
    {
        if(left >= right) return -1;

        int mid = (left + right)/2;
        if(nums[mid] == target) return mid;

        int ans = -1;
        if(nums[left] <= nums[mid])
        {
            if(nums[mid] > target && nums[left] <= target)
            {
                ans = s(nums, left, mid, target);
            }
            else ans = s(nums, mid+1, right, target);
        }

        if(nums[left] >= nums[mid] && ans == -1)
        {
            if(nums[mid] < target && nums[right-1] >= target)
            {
                ans = s(nums, mid+1, right, target);
            }
            else ans = s(nums, left, mid, target);
        }

        return ans;
    }
    int search(vector<int>& nums, int target) {

        return s(nums, 0, nums.size(), target) != -1;
    }
};