Medium

题目描述

整数数组 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

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

解题思路

这是旋转排序数组搜索问题的进阶版本，主要难点在于数组中存在重复元素。我们仍然可以使用二分搜索，但需要特殊处理重复元素的情况。

核心思路：

  1. 基本二分搜索框架：使用左右指针进行二分搜索，每次检查中点元素。

  2. 判断有序部分：由于数组是旋转的，我们需要判断左半部分还是右半部分是有序的。通过比较 nums[left] 与 nums[mid] 的关系来判断。

  3. 重复元素处理：当 nums[left] == nums[mid] == nums[right] 时，我们无法判断哪一半是有序的。此时只能同时移动左右边界，将搜索范围缩小。

  4. 搜索策略：

    • 如果左半部分有序且目标值在范围内，搜索左半部分
    • 如果右半部分有序且目标值在范围内，搜索右半部分
    • 否则搜索另一半

时间复杂度分析： 最坏情况下（大量重复元素），可能退化到 O(n)，但平均情况下仍为 O(log n)。

代码实现

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return true;
            }
            
            // 处理重复元素的情况
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                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[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            
            if nums[mid] == target:
                return True
            
            # 处理重复元素的情况
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            # 左半部分有序
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # 右半部分有序
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return False

public class Solution {
    public bool Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return true;
            }
            
            // 处理重复元素的情况
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                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[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return false;
    }
}

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (nums[mid]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n) ~ O(n)平均情况下为 O(log n)，最坏情况（大量重复元素）为 O(n)
空间复杂度O(1)只使用常数额外空间

相关题目