当前位置：首页 > article >正文

力扣第81题搜索旋转排序数组 II

article 2024/12/5 3:37:45

题目描述

给定一个可能存在重复元素的整数数组 nums 和一个目标值 target，请你判断 target 是否存在于数组中。数组原本是按升序排序的，但在某个未知的点进行了旋转（可能没有旋转）。

示例 1：

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

示例 2：

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

约束

$\leq \text{nums.length} \leq 5000$
$-10^4 \leq \text{nums[i]} \leq 10^4$
$-10^4 \leq \text{target} \leq 10^4$

解题思路

由于数组可能包含重复元素，简单的二分查找不能完全解决问题。我们需要考虑以下几点：

旋转特性：
- 数组由两段升序数组组成，例如：[4, 5, 6, 7, 0, 1, 2]。
- 某些情况下可能无法直接判断中点属于哪段升序，例如：[1, 0, 1, 1, 1]。
处理重复元素：
- 当 nums[mid] == nums[left] == nums[right] 时，无法判断中点属于哪段升序。此时可以通过移动边界缩小范围。
二分查找的逻辑：
- 如果中间值在左段升序部分：
  - 检查目标值是否在 [left, mid) 范围。
- 如果中间值在右段升序部分：
  - 检查目标值是否在 (mid, right] 范围。

C语言实现

以下是详细的实现代码：

#include <stdbool.h>

bool search(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果找到目标值，直接返回 true
        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; // 未找到目标值
}

代码详解

主逻辑

初始化指针：
使用两个指针 left 和 right，初始化为数组的两端。
二分查找：
通过 mid = left + (right - left) / 2 找到中间值，根据旋转特性判断目标值的位置。
重复元素的处理：
如果 nums[left] == nums[mid] == nums[right]，无法判断有序区间，通过收缩边界解决：
```
left++;
right--;
```

时间复杂度

最坏情况：当数组中包含大量重复元素时，退化为线性扫描，复杂度为 $O (n)$ 。
平均情况：旋转和查找的结合，使得时间复杂度为 $O(\log n)$ 。

空间复杂度

使用了常量级别的额外空间，因此复杂度为 $O (1)$ 。

测试用例

示例 1

输入：

int nums[] = {2, 5, 6, 0, 0, 1, 2};
int target = 0;
int result = search(nums, sizeof(nums) / sizeof(nums[0]), target);
printf("%s\n", result ? "true" : "false");

输出：

true

示例 2

输入：

int nums[] = {2, 5, 6, 0, 0, 1, 2};
int target = 3;
int result = search(nums, sizeof(nums) / sizeof(nums[0]), target);
printf("%s\n", result ? "true" : "false");