Open guodongxiaren opened 4 years ago
guodongxiaren
commented
4 years ago 这道题和 搜索旋转排序数组 有点类似。都是二分法。 但也有不同，大体思路是：
一共是3次二分查找的过程。另外需要注意因为是最小下标优先，所以不洗左右山坡都查找完了再比较索引，先搜左边，找到的话就不搜右边了。
这个小技巧我一开始，竟然没意识到。所以说刷算法题，即使算法本身在工作中遇不到。在刷题过程中也能提高一些潜移默化的技巧，帮助你写业务逻辑代码的时候bug-free，或者更为简洁明快。
guodongxiaren
commented
4 years ago /**
* // 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 size = mountainArr.length();
int top = findTop(mountainArr, 0, size - 1);
int index = bsearch(mountainArr, 0, top, target, less<int>());
if (index < 0) {
index = bsearch(mountainArr, top, size - 1, target, greater<int>());
}
return index;
}
int findTop(MountainArray &mountainArr, int left, int right) {
int mid = (left + right) / 2;
if (left == right) {
return -1;
}
// 左坡
if (mountainArr.get(mid) < mountainArr.get(mid+1)) {
return findTop(mountainArr, mid, right);
} else { // 右坡
if (mountainArr.get(mid) > mountainArr.get(mid-1)) {
return mid;
}
return findTop(mountainArr, left, mid);
}
}
template <typename CMP>
int bsearch(MountainArray &m, int left, int right, int target, CMP cmp) {
while (left <= right) {
int mid = (left + right) / 2;
if (target == m.get(mid)) {
return mid;
}
if (cmp(target, m.get(mid))) {
right = mid-1;
} else {
left = mid+1;
}
}
return -1;
}
};本题我分别用递归和遍历实现了二分的过程。其实遍历的写法更好一些，也不易出错其实。
另外就是我用了greater
(这是一个交互式问题) 给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index，就请返回 -1。
何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：
首先，A.length >= 3
其次，在 0 < i < A.length - 1 条件下，存在 i 使得：
你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
注意：
对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这 不是一个正确答案。
示例 1：
示例 2：
提示：