长大后想做什么？做回小孩！

0%

LeetCode——搜索旋转排序数组II

发表于 分类于 Valine：
本文字数： 432

NO.81 搜索旋转排序数组II 中等

GkdxS0.png

思路一：二分法 本题是NO.33搜索旋转排序数组的姊妹题。区别在于本题的数组可能包含重复项。

总体思路不变依然是找到有序的一半，然后使用二分法进行查找。

相较于NO.33来说，重点是如何找到有序的那一半，采用的方式是nums[start]<nums[mid]则前半部分有序，否则后半部分有序。

本题中需要多考虑一种情况就是nums[start]==nums[mid]，无法判断哪部分有序，例如” 11101 “。当遇到这种情况我么需要做的就是让start++，去掉重复项，缩小搜索区间继续搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean search(int[] nums, int target) {
    int start=0,end=nums.length-1;
    while (start <= end) {
        int mid=start+(end-start)/2;
        //找到target
        if (nums[mid]==target)return true;
        //无法判断有序的一半，忽略重复项，继续搜索
        if (nums[mid]==nums[start]){
            start++;
            continue;
        }
        //可以判断有序的一半和NO.33方法一样，二分法缩小搜搜区间
        if (nums[mid]>nums[start]){
            if (target<nums[mid]&&target>nums[start])end=mid-1;
            else start=mid+1;
        }else {
            if (target>nums[mid]&&target<=nums[end])start=mid+1;
            else end=mid-1;
        }
    }
    return false;
}

题目最后留下的一个问题：存在重复项的情况下对时间复杂度的影响。

答：主要是影响最坏时间复杂度：例如出现了形如[1,1,1,1,1,1,1,1,1]这样的数组，当搜索不到target就会不断的start++，导致时间退化到O(n)的情况。

除了最坏情况，时间复杂度和二分法应该是一样的。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github