力扣(LeetCode)81. 搜索旋转排序数组 II(C++)

线性探测+二分查找

本题和 力扣(LeetCode)33. 搜索旋转排序数组(C++) 的唯一区别是有重复元素，思考我们之前的二分条件，是根据 $nums[0]$ 和 $nums[mid]$ 判断 $mid$ 哪一端有序，但是现在可能出现 $nums[0]=nums[mid]=nums[r]$ ，再按照 $nums[mid]$ 和 $nums[0]$ 判断有序，已经不成立了。考虑去除 $nums$ 末尾等于 $nums[0]$ 的数，避免特例，这样就可以按照 $33$ 题那样二分了。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int r = nums.size()-1;
        while(r>=0&&nums[0]==nums[r]) r--;
        if(r<0) return nums[0]==target;
        int l = 0;
        while(l<=r){
            int mid = l+((r-l)>>1);
            if(nums[0]<=nums[mid]){//左端有序
                if(target>=nums[0]&&nums[mid]>=target) r = mid -1;
                else l = mid + 1;
            }else{
                if(target<nums[0]&&nums[mid]<target) l = mid + 1;
                else r = mid - 1;
            }
        }
        if(nums.size()==l) return false;
        return nums[l]==target;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度 $O(n)$ ，线性探测的最坏时间复杂度 $O(n)$ 。

空间复杂度 $O(1)$ ，只用到常量级空间 。

致语

理解思路很重要。
欢迎读者在评论区留言，答主看到就会回复的。

AC