| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
困难 |
1827 |
第 142 场周赛 Q3 |
|
（这是一个 交互式问题 ）
给你一个 山脉数组 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 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode.cn/playground/RKhe3ave，请注意这 不是一个正确答案。
示例 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() <= 100000 <= target <= 10^90 <= mountain_arr.get(index) <= 10^9
我们先通过二分查找，找到数组中的最大值所在的下标
然后我们在前半段中使用二分查找，查找目标值所在的下标，如果找不到，再在后半段中使用二分查找，查找目标值所在的下标。
时间复杂度
# """
# 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:
def search(l: int, r: int, k: int) -> int:
while l < r:
mid = (l + r) >> 1
if k * mountain_arr.get(mid) >= k * target:
r = mid
else:
l = mid + 1
return -1 if mountain_arr.get(l) != target else l
n = mountain_arr.length()
l, r = 0, n - 1
while l < r:
mid = (l + r) >> 1
if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
r = mid
else:
l = mid + 1
ans = search(0, l, 1)
return search(l + 1, n - 1, -1) if ans == -1 else ans/**
* // This is MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* interface MountainArray {
* public int get(int index) {}
* public int length() {}
* }
*/
class Solution {
private MountainArray mountainArr;
private int target;
public int findInMountainArray(int target, MountainArray mountainArr) {
int n = mountainArr.length();
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >>> 1;
if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
r = mid;
} else {
l = mid + 1;
}
}
this.mountainArr = mountainArr;
this.target = target;
int ans = search(0, l, 1);
return ans == -1 ? search(l + 1, n - 1, -1) : ans;
}
private int search(int l, int r, int k) {
while (l < r) {
int mid = (l + r) >>> 1;
if (k * mountainArr.get(mid) >= k * target) {
r = mid;
} else {
l = mid + 1;
}
}
return mountainArr.get(l) == target ? l : -1;
}
}/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get(int index);
* int length();
* };
*/
class Solution {
public:
int findInMountainArray(int target, MountainArray& mountainArr) {
int n = mountainArr.length();
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
r = mid;
} else {
l = mid + 1;
}
}
auto search = [&](int l, int r, int k) -> int {
while (l < r) {
int mid = (l + r) >> 1;
if (k * mountainArr.get(mid) >= k * target) {
r = mid;
} else {
l = mid + 1;
}
}
return mountainArr.get(l) == target ? l : -1;
};
int ans = search(0, l, 1);
return ans == -1 ? search(l + 1, n - 1, -1) : ans;
}
};/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* type MountainArray struct {
* }
*
* func (this *MountainArray) get(index int) int {}
* func (this *MountainArray) length() int {}
*/
func findInMountainArray(target int, mountainArr *MountainArray) int {
n := mountainArr.length()
l, r := 0, n-1
for l < r {
mid := (l + r) >> 1
if mountainArr.get(mid) > mountainArr.get(mid+1) {
r = mid
} else {
l = mid + 1
}
}
search := func(l, r, k int) int {
for l < r {
mid := (l + r) >> 1
if k*mountainArr.get(mid) >= k*target {
r = mid
} else {
l = mid + 1
}
}
if mountainArr.get(l) == target {
return l
}
return -1
}
ans := search(0, l, 1)
if ans == -1 {
return search(l+1, n-1, -1)
}
return ans
}/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class Master {
* get(index: number): number {}
*
* length(): number {}
* }
*/
function findInMountainArray(target: number, mountainArr: MountainArray) {
const n = mountainArr.length();
let l = 0;
let r = n - 1;
while (l < r) {
const mid = (l + r) >> 1;
if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
r = mid;
} else {
l = mid + 1;
}
}
const search = (l: number, r: number, k: number): number => {
while (l < r) {
const mid = (l + r) >> 1;
if (k * mountainArr.get(mid) >= k * target) {
r = mid;
} else {
l = mid + 1;
}
}
return mountainArr.get(l) === target ? l : -1;
};
const ans = search(0, l, 1);
return ans === -1 ? search(l + 1, n - 1, -1) : ans;
}impl Solution {
#[allow(dead_code)]
pub fn find_in_mountain_array(target: i32, mountain_arr: &MountainArray) -> i32 {
let n = mountain_arr.length();
// First find the maximum element in the array
let mut l = 0;
let mut r = n - 1;
while l < r {
let mid = (l + r) >> 1;
if mountain_arr.get(mid) > mountain_arr.get(mid + 1) {
r = mid;
} else {
l = mid + 1;
}
}
let left = Self::binary_search(mountain_arr, 0, l, 1, target);
if left == -1 {
Self::binary_search(mountain_arr, l, n - 1, -1, target)
} else {
left
}
}
#[allow(dead_code)]
fn binary_search(m: &MountainArray, mut l: i32, mut r: i32, k: i32, target: i32) -> i32 {
let n = m.length();
while l < r {
let mid = (l + r) >> 1;
if k * m.get(mid) >= k * target {
r = mid;
} else {
l = mid + 1;
}
}
if m.get(l) == target {
l
} else {
-1
}
}
}