给你一个 山脉数组 mountainArr
,请你返回能够使得 mountainArr.get(index)
等于 target 最小 的下标 index 值。
如果不存在这样的下标 index,就请返回 -1。
何为山脉数组?如果数组 A 是一个山脉数组的话,那它满足如下条件:
首先,A.length >= 3
其次,在 0 < i < A.length - 1
条件下,存在 i 使得:
A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]
你将 不能直接访问该山脉数组,必须通过 MountainArray 接口来获取数据:
MountainArray.get(k)
- 会返回数组中索引为k 的元素(下标从 0 开始)
MountainArray.length()
- 会返回该数组的长度
注意:
对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案
示例 1:
输入:array = [1,2,3,4,5,3,1], target = 3
输出:2
解释:3 在数组中出现了两次,下标分别为 2 和 5,我们返回最小的下标 2。
示例 2:
输入:array = [0,1,2,4,2,1], target = 3
输出:-1
解释:3 在数组中没有出现,返回 -1。
提示:
3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-in-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路及算法
通过峰值元素,可以将原数组在逻辑上一分为二,分出来的两个子数组分别有序。
然后分别对 左边子数组 和 右边子数组 进行查找即可,两个数组均不满足则返回 -1
查找峰值元素
通过题目了解和直观的判断,我们可以知道 当一个数既大于左邻居数又大于右邻居数时,这个数就是峰值元素
于是乎,我们可以使用二分查找的方法找到 峰值元素
def find_peak_index(left, right):
while left + 1 < right:
mid = (left + right) >> 1
x = mountain_arr.get(mid) # 中间元素
y = mountain_arr.get(mid+1) # 右邻居元素
z = mountain_arr.get(mid-1) # 左邻居元素
if x > y and x > z:
# 找到峰值
return mid
elif y >= x >= z:
left = mid
elif y <= x <= z:
right = mid
因为两个子数组有着明显差异,一个升序,一个降序,所以收缩边界的条件可以进行优化
- 当mid位置的元素大于右邻居元素时
arr[mid] > arr[mid + 1]
mid落在了降序的子数组中,峰值在其左侧,所以收缩右边界 right = mid,因为当前 mid 的值刚好可能是峰值,所以这里就不 +1
- 反面
arr[mid] <= arr[mid + 1]
mid落在了升序的子数组中,峰值在其右侧,所以收缩左边界 left = mid + 1,因为 mid 小于右邻居元素,所以它不可能是峰值元素,所以这里可以 +1
def find_peak_index(left, right):
while left < right:
mid = (left + right) >> 1
if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
right = mid
else:
left = mid + 1
return left
查找target元素
如果存在重复元素,按题目要求应该返回索引值较小的,所以我们先查找升序数组。
这一步依然是使用二分查找
def binary_search(left, right, v):
while left <= right:
mid = (left + right) >> 1
mid_value = mountain_arr.get(mid)
if mid_value < target:
if v:
left = mid + 1
else:
right = mid - 1
elif mid_value > target:
if v:
right = mid - 1
else:
left = mid + 1
else:
return mid
return -1
为了减少代码量,使升序数组和降序数组都可以使用,则新增一个布尔值,用于判断当前数组是升序还是降序
完整代码
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
# def get(self, index: int) -> int:
# def length(self) -> int:
class Solution:
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
# nums[i] > nums[i+1] 表示i是峰值元素
size = mountain_arr.length()
left = 0
right = size - 1
def find_peak_index(left, right):
while left + 1 < right:
mid = (left + right) >> 1
if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
right = mid
else:
left = mid + 1
return right
def binary_search(left, right, v):
while left <= right:
mid = (left + right) >> 1
mid_value = mountain_arr.get(mid)
if mid_value < target:
if v:
left = mid + 1
else:
right = mid - 1
elif mid_value > target:
if v:
right = mid - 1
else:
left = mid + 1
else:
return mid
return -1
peak = find_peak_index(left, right)
l = binary_search(left, peak, True)
if l != -1: return l
r = binary_search(peak+1, right, False)
return r if r != -1 else -1