leetcode
leetcode 1001 ~ 1050
山脉数组中查找目标值

山脉数组中查找目标值

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.7 MB


/*
 * 使用Java Stream的题解实际上不适合,因为这是一个交互式问题,
 * 并且我们无法直接访问数组,只能通过MountainArray接口获取值。
 * 因此Java Stream无法直接用于该问题的求解。
 * 下面提供了一个简要的伪代码以供参考,表明了Stream在这种情境中的不适用性。
 */

interface MountainArray {
    public int get(int index);
    public int length();
}

public class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        // 使用Stream API查找峰顶元素 (伪代码,仅作为解释说明)
        int peak = IntStream.range(0, mountainArr.length())
                             .boxed()
                             .max((a, b) -> mountainArr.get(a) - mountainArr.get(b))
                             .orElse(-1);
        // 由于无法直接访问数组元素,无法在实际代码中使用Stream进行查找
        // 需要按照Java解法中的逻辑实现
        return -1; // Stream不适用于交互式问题的实际实现
    }
}

解释

方法:

这个解决方案首先利用二分搜索找到山脉数组的峰值,即从左到右最大的元素,这个元素将数组分为递增和递减两部分。找到峰值后,解决方案再次使用二分搜索在递增部分查找目标值。如果在递增部分找到了目标值,直接返回其索引。如果没有找到,再在递减部分使用二分搜索查找目标值。如果在任何部分都没有找到目标值,则返回-1。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆
在使用二分搜索找到山脉数组的峰值时,你是如何确定峰值的确切位置的?
在二分搜索过程中,我们比较中间元素和其右侧相邻的元素。如果中间元素小于其右侧元素,则表明峰值位于中间元素的右侧(包括中间元素的右侧元素),因此我们将搜索区间调整为右侧部分,即移动左边界`left`到`mid + 1`。反之,如果中间元素大于或等于其右侧元素,则峰值位于中间元素的左侧(包括中间元素本身),因此我们将搜索区间调整为左侧部分,即移动右边界`right`到`mid`。最终当`left`等于`right`时,它们指向的位置即为峰值位置。
🦆
为什么在找到峰值之后需要分别在递增和递减部分进行二分搜索,这种方法的有效性是基于什么原理?
山脉数组的定义是先递增再递减,因此在找到峰值后,我们可以明确两个部分:左侧部分是递增的,右侧部分是递减的。递增部分和递减部分都是单调的,这使得我们可以分别在这两个部分使用二分搜索来高效查找目标值。二分搜索有效的前提是数据的单调性,单调递增或递减的数组允许我们通过比较中间值与目标值来快速决定继续搜索的方向,从而有效地减少搜索范围。
🦆
在递增和递减部分的二分搜索中,你是如何根据数组的增减性质修改二分搜索条件的?
在递增部分的二分搜索中,如果中间元素小于目标值,则目标值可能位于中间元素的右侧,因此我们将左边界`left`移动到`mid + 1`。如果中间元素大于目标值,目标值可能位于中间元素的左侧,因此我们将右边界`right`移动到`mid - 1`。在递减部分的二分搜索中,逻辑相反:如果中间元素大于目标值,则目标值可能位于中间元素的右侧,因此我们将左边界`left`移动到`mid + 1`;如果中间元素小于目标值,则目标值可能位于中间元素的左侧,因此我们将右边界`right`移动到`mid - 1`。这样的调整是为了确保我们总是向可能包含目标值的区域缩小搜索范围。

相关问题