二分查找
解题思路
第一次二分找到峰值的索引，将山脉数组分成左右两段，左段时递增序列，右段是递减序列；
第二次二分找到左段序列的 target 索引，如果找到了直接返回，无需进行第三步，因为题意是要最小的 target 索引；
第三次二分找到右段序列的 target 索引；
复杂度
-
时间复杂度：
O(logn) -
空间复杂度：
O(1)
代码实现
var findInMountainArray = function (target, mountainArr) {
// 1. 获取峰值索引，并将山脉数组分成2段
let peakInx = peakIndexInMountainArray(mountainArr);
// 2. 在左侧山脉数组中寻找 target
let leftInx = peakIndexINLeftMountainArray(target, mountainArr, 0, peakInx);
if (leftInx !== -1) {
return leftInx;
}
// 3. 在右侧山脉数组中寻找 target
let rightInx = peakIndexINRighrMountainArray(target, mountainArr, peakInx + 1, mountainArr.length() - 1);
if (rightInx !== -1) {
return rightInx;
}
return -1;
};
// 获取峰值索引
var peakIndexInMountainArray = function (mountainArr) {
let left = 0;
let right = mountainArr.length() - 1;
while (left <= right) {
let mid = (left + right) >>> 1;
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) { // 左侧山脉序列是递增的
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
};
var peakIndexINLeftMountainArray = function (target, mountainArr, left, right) {
while (left <= right) {
let mid = (left + right) >>> 1;
if (mountainArr.get(mid) < target) {
left = mid + 1;
} else if (mountainArr.get(mid) > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
var peakIndexINRighrMountainArray = function (target, mountainArr, left, right) {
while (left <= right) {
let mid = (left + right) >>> 1;
if (mountainArr.get(mid) < target) {
right = mid - 1;
} else if (mountainArr.get(mid) > target) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 242. 有效的字母异位词
上一篇
评论
