| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
困难 |
1827 |
第 142 场周赛 Q3 |
|
（这是一个 交互式问题 ）
你可以将一个数组 arr 称为 山脉数组 当且仅当：
arr.length >= 3- 存在一些
0 < i < arr.length - 1的i使得：arr[0] < arr[1] < ... < arr[i - 1] < arr[i]arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给定一个山脉数组 mountainArr ，返回 最小 的 index 使得 mountainArr.get(index) == target。如果不存在这样的 index，返回 -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() <= 1040 <= target <= 1090 <= mountain_arr.get(index) <= 109
我们先通过二分查找，找到数组中的最大值所在的下标
然后我们在前半段中使用二分查找，查找目标值所在的下标，如果找不到，再在后半段中使用二分查找，查找目标值所在的下标。
时间复杂度
# """
# 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
}
}
}