文章

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

题目链接

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

题目描述

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

在传递给函数之前,nums 在预先未知的某个下标 k0 <= 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)。这种在部分有序数组上进行二分查找的技巧,在搜索类问题中非常常见。

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

License:  CC BY 4.0