leetcode81.Search in Rotated Sorted Array II

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
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.

相比于I，II中添加了数组中可能存在重复值的条件。大家可以先参考一下我的这篇关于I的博客，在这个基础上，考虑如何实现这道题目。

思路与代码

在上一道题目的基础上，我们知道，如果数组中存在重复值，可能会出现类似于[1,3,1,1]这种情况出现。如果在这时候使用二分法，很可能会无法判断出到底属于左半侧数组还是右半侧数组。这是我们可以将情况分为以下几种。

  1. 目标值位于左侧上升数组中，也就是说nums[left]<target<nums[mid]
  2. 目标值位于右侧上升数组中，也就是说nums[mid]<target<nums[right]
  3. 其它情况
    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
    public boolean search(int[] nums, int target) {
        int left = 0 , right = nums.length-1;
        while(left<=right){
            int mid = ( left + right ) / 2;
            if(nums[mid] == target){
                return true;
            }else if(nums[left] < nums[mid]){
                if(target>=nums[left] && target<=nums[mid]){
                    right = mid-1;
                }else{
                    left = mid + 1;
                }
            }else if(nums[mid] < nums[right]){
                if(target>=nums[mid] && target<=nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            //判断左右节点是否为目标值，不是则分别调整
            }else{
                if(nums[left] == target || nums[right] == target){
                    return true;
                }else{
                    left++;
                    right--;
                }
            }
        }
        return false;
    }

简单优化

在第三种情况下，我们可以看到该类别满足nums[left]>=nums[mid]且nums[mid]>=nums[right]。这时候，我们可以分析一下，

  1. 如果nums[mid]>nums[right]，那么nums[mid]=nums[left]。因为如果nums[mid]>nums[right]而且nums[mid]<nums[left]，则mid左侧或右侧的子数组至少有一个为desc顺序的数组，这违背题目要求。所哟一定是nums[mid]=nums[left]
  2. 同理，如果nums[mid]<nums[left]，那么nums[mid]=nums[left]’。
  3. nums[mid]=nums[left]=nums[right]!=target

代码如下：

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
public boolean search2(int[] nums, int target){
    int left = 0 , right = nums.length-1;
    while(left<=right){
        int mid = ( left + right ) / 2;
        if(nums[mid] == target){
            return true;
        }else if(nums[left] < nums[mid]){
            if(target>=nums[left] && target<=nums[mid]){
                right = mid-1;
            }else{
                left = mid + 1;
            }
        }else if(nums[mid] < nums[right]){
            if(target>=nums[mid] && target<=nums[right]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
            
        //精华第三种场景
        }else if(nums[mid] > nums[right]){
            left = mid + 1;
        }else if(nums[mid] < nums[left]){
            right = mid - 1;
        }else{
            left++;
            right--;
        }
    }
    return false;
}