LeetCode 81. Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

题目描述

• 难度：Medium
• Tag: Binary Search

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Step 1. 找出最小元素：不考虑重复

一个数组在一个未知的下标处进行了旋转，要求我们在旋转后的数组中找到目标元素。不论用什么解法，首先我们需要找到数组是从哪里开始的。如果不考虑重复元素的情况，这一步其实就是 153. Find Minimum in Rotated Sorted Array。

假设数组是从 n-k 处开始的，那么一种暴力解就是倒序遍历，线性查找出 k ，然后将数组再拼接成旋转之前的状态，之后再用二分查找找到目标即可。这种情况最坏时间和空间复杂度都是 O(N) 。

更好的方法是用二分查找找出最小的元素，它所在的下标就是数组开始的位置：

const n = nums.length;
let left = 0, right = n - 1;
while(left < right) {
    const mid = left + Math.floor((right-left)/2);
    // 如果 mid 比右边界大，说明数组至少得是从 mid+1 开始
    if (nums[mid] > nums[right]) {
        left = mid + 1;
    }
    // 如果 mid 比右边界小，说明从 mid 到右边界的部分数组是没问题的，k 只能在 mid 左边
    else if (nums[mid] < nums[right]) {
        right = mid;
    }
}
// 现在的left就是数组开始的地方
const start = left;

Step 2. 二分查找：不考虑重复元素

在不考虑有重复元素的情况下，这道题其实就是 33. Search in Rotated Sorted Array。我们现在已经得知了数组的起始下标 start，我们将数组看成是左右两部分有序数组。将 start 所在的元素与 target 进行比较，如果它大于 target，则在左半部分进行搜索，反之则在右半部分：

// 别忘记给 left 和 right 复位
left = 0;
right = n - 1;
if (target >= nums[start] && target <= nums[n - 1]) {
    left = start;
} else {
    right = start - 1;
}
// Binary search
while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] > target) right = mid - 1;
    else if (nums[mid] < target) left = mid + 1;
    else return true;
}

Step 3. 含有重复元素的情况

到目前为止，我们都假设了数组没有重复的元素，也就是解决了 33. Search in Rotated Sorted Array 问题。

那么如果数组有重复元素，应该怎么做呢？

其实重复元素影响的只是我们找寻起始位置的步骤，在循环里判断一下，在 mid 与右边界相等的情况下对左右边界进行线性逼近，直到遇到不重复元素为止。这种解法最坏时间复杂度为 O(N)。

// Find where the array starts
let left = 0;
let right = n - 1;
while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] > nums[right]) left = mid + 1;
    else if (nums[mid] < nums[right]) right = mid;
    else {
        while (left < right && nums[right] === nums[right - 1]) right--;
        while (left < right && nums[left] === nums[left + 1]) left++;
    }
}
const start = left;

完整代码

function search(nums: number[], target: number): boolean {
    const n = nums.length;
    if (n === 1) return nums[0] === target;
    // Find where the array starts
    let left = 0;
    let right = n - 1;
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] > nums[right]) left = mid + 1;
        else if (nums[mid] < nums[right]) right = mid;
        else {
            while (left < right && nums[right] === nums[right - 1]) right--;
            while (left < right && nums[left] === nums[left + 1]) left++;
        }
    }
    const start = left;
    // Determine which half to search
    left = 0;
    right = n - 1;
    if (target >= nums[start] && target <= nums[n - 1]) {
        left = start;
    } else {
        right = start - 1;
    }
    // Binary search
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] > target) right = mid - 1;
        else if (nums[mid] < target) left = mid + 1;
        else return true;
    }
    return false;
}