跳至主要內容

1095. 山脉数组中查找目标值

ITCharge大约 2 分钟

1095. 山脉数组中查找目标值open in new window

  • 标签:数组、二分查找、交互
  • 难度:困难

题目链接

题目大意

描述:给定一个山脉数组 mountainArrmountainArr

要求:返回能够使得 mountainArr.get(index) 等于 targettarget 最小的下标 indexindex 值。如果不存在这样的下标 indexindex,就请返回 1-1

说明

  • 山脉数组:满足以下属性的数组:

    • len(arr)3len(arr) \ge 3
    • 存在 ii0<i<len(arr)10 < i < len(arr) - 1),使得:
      • arr[0]<arr[1]<...arr[i1]<arr[i]arr[0] < arr[1] < ... arr[i-1] < arr[i];
      • arr[i]>arr[i+1]>...>arr[len(arr)1]arr[i] > arr[i+1] > ... > arr[len(arr) - 1]
  • 不能直接访问该山脉数组,必须通过 MountainArray 接口来获取数据:

    • MountainArray.get(index):会返回数组中索引为 kk 的元素(下标从 00 开始)。

    • MountainArray.length():会返回该数组的长度。

  • MountainArray.get 发起超过 100100 次调用的提交将被视为错误答案。

  • 3mountainarr.length()100003 \le mountain_arr.length() \le 10000

  • 0target1090 \le target \le 10^9

  • 0mountainarr.get(index)1090 \le mountain_arr.get(index) \le 10^9

示例

  • 示例 1:
输入:array = [1,2,3,4,5,3,1], target = 3
输出:2
解释:3 在数组中出现了两次,下标分别为 25,我们返回最小的下标 2
  • 示例 2:
输入:array = [0,1,2,4,2,1], target = 3
输出:-1
解释:3 在数组中没有出现,返回 -1

解题思路

思路 1:二分查找

因为题目要求不能对 MountainArray.get 发起超过 100100 次调用。所以遍历数组进行查找是不可行的。

根据山脉数组的性质,我们可以把山脉数组分为两部分:「前半部分的升序数组」和「后半部分的降序数组」。在有序数组中查找目标值可以使用二分查找来减少查找次数。

而山脉的峰顶元素索引也可以通过二分查找来做。所以这道题我们可以分为三步:

  1. 通过二分查找找到山脉数组的峰顶元素索引。
  2. 通过二分查找在前半部分的升序数组中查找目标元素。
  3. 通过二分查找在后半部分的降序数组中查找目标元素。

最后,通过对查找结果的判断来输出最终答案。

思路 1:代码

#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def binarySearchPeak(self, mountain_arr) -> int:
        left, right = 0, mountain_arr.length() - 1
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        return left

    def binarySearchAscending(self, mountain_arr, left, right, target):
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) < target:
                left = mid + 1
            else:
                right = mid
        return left if mountain_arr.get(left) == target else -1

    def binarySearchDescending(self, mountain_arr, left, right, target):
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) > target:
                left = mid + 1
            else:
                right = mid
        return left if mountain_arr.get(left) == target else -1

    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        size = mountain_arr.length()
        peek_i = self.binarySearchPeak(mountain_arr)

        res_left = self.binarySearchAscending(mountain_arr, 0, peek_i, target)
        res_right = self.binarySearchDescending(mountain_arr, peek_i + 1, size - 1, target)
        
        return res_left if res_left != -1 else res_right

思路 1:复杂度分析

  • 时间复杂度O(logn)O(\log n)
  • 空间复杂度O(1)O(1)