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

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

33.搜索旋转排序数组不同的是,数组中的元素可以重复

比如:数组【0 0 1 2 2 5 6】
经旋转变成【2 5 6 0 0 1 2】

解法一:顺序查找

解法二:二分查找

分析:

经过旋转后的数组,只是局部有序,整体并不有序,且有重复的元素,本题如何应用二分?

在开始的判断中,与33.搜索旋转排序数组题解原理相同,根据中间元素 mid ,将序列划分为 [low,mid-1]mid[mid+1,high]

  1. 如果target == nums[mid] ,代表找到了该元素,直接返回即可;
  2. 否则,进行下面的处理。

在比较targetnums[mid] 之前,先比较 nums[low]nums[mid] 的关系,原理如下:

第一类序列:【2 3 3 4 6 1 2】,也就是 nums[low] < nums[mid] ,此例中为2<5。这种情况下,可以保证序列的前半部分是有序的。

  • 如果 nums[low] <= target < nums[mid] ,则去前半部分找
  • 否则,去后半部分找

第二类序列:【6 1 2 2 3 3 4】,也就是 nums[low] > nums[mid] ,此例中为6>2。这种情况下,可以保证序列的后半部分是有序的。

  • 如果 nums[mid] <= target < nums[end] ,则去后半部分找
  • 否则,去前半部分找

(至此,与33.搜索旋转排序数组题解解法一致)

第三类序列:【1 0 0 1 1 1 1】,这种情况下 nums[low] == nums[mid] ,这个时候无法判断是前半部分有序还是后半部分有序。

无法判断的原因:

如序列【0 0 1 1 1 1 1】可以经过旋转变成上面的【1 0 0 1 1 1 1】,也可以旋转成【1 1 1 1 0 0 1】,这两种情况都是 nums[low] == nums[mid]

如果根据【1 0 0 1 1 1 1】将这种序列判断成右序列有序,而0不在nums[3]nums[6],即11之间,就去左序列找,这样可能找到0。

但这样就会导致处理第二种序列【1 1 1 1 0 0 1】时,也认为右边有序,0不在1~1之间,就去左序列找,最后导致序列中有0,但返回false的结果。

(这也给我一个提醒,做算法题的时候,不要根据自己举的一个例子,或者根据题目中的一个例子去设计算法,而是根据一个适用性的规律来设计)

  • 直接 low++ 即可,相当于去掉一个重复的干扰项。
    • 既然到了判断nums[low]nums[mid] 的关系的环节,说明 nums[mid] 不是要找的target,而 nums[low] == nums[mid] ,所以nums[low] 也不是target,所以直接low++,不会影响查找的结果,而且可以去除重复的干扰项

代码:

bool rotateSearch2(vector<int>& nums, int target){
    if(nums.size()==0) return -1;
    int low=0,high=nums.size()-1;
    while(low<=high){
        int mid = low+(high-low)/2;
        if(nums[mid]==target) return true;
        else if(nums[low]<nums[mid]){
            if(nums[low]<=target && target<nums[mid]){ //mid's left 
                high=mid-1;
            }else { //mid's right
                low=mid+1;
            }
        }else if(nums[low]>nums[mid]){
            if(nums[mid]<target && target<=nums[high]){ //mid's right
                low=mid+1;
            }else { //mid's left
                high = mid-1;
            }
        }else {  //nums[low]==nums[mid]
            //low与mid 重复,直接跳过重复项,在[low+1,high]中继续二分查找
            low++;
        }
    } 
    return false;
}
上一篇:81.搜索旋转排序数组II(中等)


下一篇:冒个泡,排个序