[LeetCode] 每日一题 81. 搜索旋转排序数组 II

题目链接

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii

题目描述

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 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

提示

• 1 <= nums.length <= 5000

• -10^4 <= nums[i] <= 10^4

• 题目数据保证 nums 在预先未知的某个下标上进行了旋转

• -10^4 <= target <= 10^4

解题思路

本题是 搜索旋转排序数组 的变种，数组在某个未知的下标 k 处进行了旋转，同时允许数组中包含重复元素。由于数组是部分有序的，因此可以使用二分查找，但需要额外处理重复元素的情况

核心思路：

1. 标准二分查找框架：

   • 计算 mid 并判断 nums[mid] 是否等于 target，若相等则直接返回 true

   • 由于旋转导致数组部分有序，因此需要根据 nums[mid] 与 nums[left] 及 nums[right] 的关系来判断哪一部分是有序的

2. 特殊情况处理：

   • 当 nums[left] == nums[mid] == nums[right] 时，无法确定哪一部分是有序的，例如 nums = [3,1,2,3,3,3,3]，target = 2

   • 在这种情况下，我们只能通过缩小搜索区间来规避无法判断的问题，即将左边界右移 left++，将右边界左移 right--，然后继续二分查找

3. 有序区间的判定：

   • 若 nums[left] <= nums[mid]，说明 左侧区间 [left, mid] 是有序的：

     • 若 target 在 [nums[left], nums[mid]] 之间，则搜索左侧 right = mid - 1，否则搜索右侧 left = mid + 1

   • 若 nums[left] > nums[mid]，说明 右侧区间 [mid, right] 是有序的：

     • 若 target 在 [nums[mid], nums[right]] 之间，则搜索右侧 left = mid + 1，否则搜索左侧 right = mid - 1

由于最坏情况下数组中所有元素都相等，可能需要遍历整个数组，因此最坏时间复杂度是 O(n)，但通常情况下仍可保证 O(log n) 的效率

代码实现

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums.length == 0) {
            return false;
        }
        if (nums.length == 1) {
            return nums[0] == target;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[left] == nums[mid] && nums[right] == nums[mid]) {
                left++;
                right--;
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.length - 1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：

  • 最坏情况下 O(n)：当所有元素都相等且不等于 target 时，我们需要遍历整个数组，例如 nums = [2,2,2,2,2]，target = 3

  • 一般情况下 O(log n)：当 nums[left] != nums[mid] 或 nums[mid] != nums[right] 时，二分查找仍可有效缩小搜索区间

• 空间复杂度：

  • O(1)，仅使用了几个额外变量，没有额外的空间消耗

总结

本题的关键在于二分查找时如何处理重复元素，由于 nums[left] == nums[mid] == nums[right] 的情况会导致无法判断哪一部分是有序的，因此我们只能逐步缩小搜索区间，直到可以正常执行二分。通常情况下，二分查找仍能保持 O(log n) 的复杂度，但在极端情况下会退化为 O(n)。这种在部分有序数组上进行二分查找的技巧，在搜索类问题中非常常见。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。