题目描述

题目链接

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

样例

1
2
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
1
2
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

算法1

(暴力枚举) $O(n)$

由于题目数据范围比较小，因此可以直接暴力枚举数组中每个元素，并于目标值进行比较即可

算法2

(二分查找) $O(log(n))$

这道题是 LeetCode 33.搜索旋转排序数组 的变种；
在 LC_33 中，数据保证了数组中不含有重复的元素，那么整个数组是具有二段性的，因此可以直接使用二分查找

在本题中，由于数组中含有重复元素，在旋转之后有可能会破坏原有的二分性质，因此需要在二分之前进行预处理，去掉某一部分中的重复元素，之后即可进行二分查找

如图所示，在二分时会出现无法判断属于前半部分还是后半部分的情况，因此需要对其中的一个部分删去重复元素，还原二分性质

lc81_1

C++ 代码

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
33
34
35
36
37
class Solution {
public:
    bool find(vector<int>& nums, int l, int r, int target)
    {
        while( l < r)
        {
            int mid = (l + r) >> 1;
            if( nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if( nums[r] == target) return true;
        return false;
    }

    bool search(vector<int>& nums, int target) {
        if( nums.size() == 1)   return target == nums[0];
        int k = nums.size() - 1;
        while( k && nums[k] == nums[0]) k --, nums.pop_back();
        int n = nums.size();
        int l = 0, r = n - 1;
        while( l < r)
        {
            int mid = (l + r + 1) >> 1;
            if( nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        bool flag = false;
        if( r < n - 1)
        {
            flag = find(nums, 0, r, target) || find(nums, r + 1, n - 1, target);
        }
        else flag = find(nums, 0, r, target);
        

        return flag;
    }
};