搜索旋转排序数组 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⁴ <= nums[i] <= 10⁴
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10⁴ <= target <= 10⁴

进阶：

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

代码结果

运行时间: 40 ms, 内存: 15.4 MB

/*
题目思路：
1. 在Java中利用流操作实现目标值查找。
2. 使用流的任何匹配(anyMatch)方法来检查是否存在目标值。
3. 通过对数组进行stream转换后检查流中是否有目标值。
4. 这种方法虽然简洁但不适用于大规模数据集，因为其不保证最优时间复杂度。
*/
 
import java.util.Arrays;
 
public class Solution {
    public boolean search(int[] nums, int target) {
        return Arrays.stream(nums).anyMatch(num -> num == target);
    }
}

解释

方法:

该题解采用二分查找的思路。首先去除数组末尾与开头相等的元素,缩小搜索范围。然后通过二分查找定位旋转点的位置,将数组分为两个有序数组。最后根据目标值与开头值的大小关系,确定在哪一个有序数组中二分查找目标值。

时间复杂度:

O(logn)

空间复杂度:

O(1)

代码细节讲解

🦆

在去除数组末尾与开头相等的元素后，如果数组变为空怎么处理？

▷

如果在去除数组末尾与开头相等的元素后数组变为空，意味着所有元素都是相同的，并且都等于数组的第一个元素。在这种情况下，只需要检查目标值是否与这个相同的元素相等。如果相等，则返回True，否则返回False。这种情况可以通过在二分查找开始之前添加一个检查来处理，如果数组长度为0，则直接根据目标值与数组第一个元素的比较结果返回。

🦆

为什么在二分查找旋转点时，选择`mid`索引的计算方法为`l + (r - l + 1) // 2`而不是常见的`l + (r - l) // 2`？

▷

在二分查找中使用`mid = l + (r - l + 1) // 2`的计算方式是为了确保当`l`和`r`非常接近时，`mid`能够偏向右侧，这有助于避免死循环并保证搜索范围能够稳定缩减。特别是在寻找旋转点的上下文中，这种方法能更精确地处理边界条件，确保不会漏掉旋转点的检测。

🦆

在确定旋转点后，如果`target`等于`nums[0]`，应该如何确定它的存在性？

▷

如果在确定旋转点后，`target`等于`nums[0]`，由于旋转排序数组的特性，`nums[0]`是旋转点左侧数组的最小元素，并且是右侧数组的最大元素。因此，如果`target`等于`nums[0]`，可以直接返回True，因为`nums[0]`是明确存在于数组中的。

🦆

为什么在确定二分查找的区间时，使用`target >= nums[0]`而不是检查`target`是否在两个有序数组的范围内？

▷

使用`target >= nums[0]`而不是检查`target`是否在两个有序数组的范围内是因为，旋转排序数组分割成的两个部分之一始终包含数组的第一个元素`nums[0]`，并且这一部分数组是完全有序的。因此，只需检查`target`是否大于等于`nums[0]`来确定`target`是否可能位于这个有序部分。这简化了逻辑并减少了条件判断，使得算法更为高效和清晰。

相关问题