81. 搜索旋转排序数组 II

本题来自 LeetCode：81. 搜索旋转排序数组 II^[1]

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6]可能变为 [2,5,6,0,0,1,2])。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例  1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例  2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

进阶:
这是 搜索旋转排序数组   的延伸题目，本题中的 nums可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

题目分析

本题和 33. 搜索旋转排序数组题，最大的不同在于，可以出现重复元素。那出现重复元素，可能有哪些影响？先引用在分析题 153. 寻找旋转排序数组中的最小值所总结的规律。

要进行二分法剪枝的话，就必须确定好哪部分子数组是有序的。那么需要通过区间[left...mid...right]来判断左子区间[left...mid]和右左子区间[mid...right]哪部分是有序的。这个就很好判断了，因为我们知道nums[left]、nums[mid]、nums[right]这三者的值；

若旋转的`不是`重复元素，比如`[5,6,0,0,1,2,2]`，可以发现，我们可以还是可以通过`nums[left]、nums[mid]、nums[right]这三者的值`还判断哪边是有序的。依然可以采用`33. 搜索旋转排序数组`的解法。

若旋转的`是`重复元素，比如`[2,5,6,0,0,1,2]`，可以发现，由于`nums[left] = nums[right]`，这时，无法通过这三者来确定哪边是有序的。这个时候，需要移除其中一个元素，防止干扰`步骤1`的判断。可以通过`left++`或者`right --`来实现。

题目解答

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left = right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return true;
            }
            // [left...right]有序，target必然在区间[left...right]中
            if(nums[left]  nums[right]) {
                if(nums[mid]  target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else if(nums[left]  nums[right]) {
                // 表示[mid...right]是有序的，需要判断target是否位于[mid...right]内
                if(nums[mid] = nums[right]) {
                    // target在区间[mid...right]中
                    if(nums[mid]  target && target = nums[right]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                // 表示[left...mid]是有序的，需要判断target是否位于[left...mid]内
                } else if(nums[mid]  nums[right]) {
                    // target在区间[left...mid]中
                    if(nums[left] = target && target  nums[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
            } else {
                    // 和 33. 搜索旋转排序数组 的不同点
                if(left == right) {
                    return false;
                } else {
                        // 移除掉nums[left]的干扰
                    left ++;
                }
            }
        }
        return false;
    }
}

复杂度分析：
时间复杂度： O(n)，可能退化成对数组的顺序遍历
空间复杂度： O(1)

参考资料

81. 搜索旋转排序数组 II: https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/

原文始发于微信公众号（xiaogan的技术博客）：