leetcode 81. 搜索旋转排序数组 II

叁歲伎倆 2023-07-05 10:18 23阅读 0赞

这题和 搜索旋转排序数组 唯一的区别就是可能会有重复的元素。

也就是会出现\[1,3,1,1\]这样的数据。之前无重复时，我们可以断定，二分的点一定属于某个有序序列。但现在不行了，例如取mid=2,此时,nums\[0\]==nums\[2\]，无法断定mid属于前一段还是后一段。不过有一个思路就是，既然nums\[mid\]==nums\[l\]，那么nums\[mid\]不是我们想要的，那么nums\[l\]也必然不是。所以l++,即可。

代码和之前的一题几乎一样。

class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int n=nums.size();
            int l=0,r=n-1;
            int ans=-1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(nums[mid]>nums[l])
                {
                    int tmp=two(nums,target,l,mid);
                    if(tmp==-1)
                    {
                        l=mid+1;
                    }
                    else
                    {
                        ans=tmp;
                        break;
                    }
                }
                else if(nums[mid]<nums[r])
                {
                    int tmp=two(nums,target,mid,r);
                    cout<<tmp<<endl;
                    if(tmp==-1)
                    {
                        r=mid-1;
                    }
                    else
                    {
                        ans=tmp;
                        break;
                    }
                }
                else if(nums[mid]==target)
                {
                    ans=mid;
                    break;
                }
                else if(nums[mid]==nums[l])
                {
                    l++;
                }
                else if(nums[mid]==nums[r])
                {
                    r--;
                }
            }
            return ans==-1?false:true;
        }
        int two(vector<int>& nums, int target,int l,int r)
        {
            int ans=-1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(nums[mid]>target)
                {
                    r=mid-1;
                }
                else if(nums[mid]<target)
                {
                    l=mid+1;
                }
                else
                {
                    ans=mid;
                    break;
                }
            }
            return ans;
        }
    };