leetcode 1095. 山脉数组中查找目标值
给你一个 山脉数组 mountainArr,请你返回能够使得mountainArr.get(inde x) 等于 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
题解:
1.一个 山脉数组
2.求山脉数组中等于 target 的最小下标 index
3.不存在这样的下标 index,返回 -1
4.对 MountainArray.get发起超过100次调用的提交将被视为错误答案
示例 1:
输入:candies = 7, num_people = 4
输出:[1,2,3,1]
解释:
第一次,ans[0] += 1,数组变为 [1,0,0,0]。
第二次,ans[1] += 2,数组变为 [1,2,0,0]。
第三次,ans[2] += 3,数组变为 [1,2,3,0]。
第四次,ans[3] += 1(因为此时只剩下 1 颗糖果),最终数组变为 [1,2,3,1]。
示例 2:
输入:candies = 10, num_people = 3
输出:[5,2,3]
解释:
第一次,ans[0] += 1,数组变为 [1,0,0]。
第二次,ans[1] += 2,数组变为 [1,2,0]。
第三次,ans[2] += 3,数组变为 [1,2,3]。
第四次,ans[0] += 4,最终数组变为 [5,2,3]。
解题思路:二分查找的应用
-
单从对get函数的调用次数不能超过一百次,应考虑二分查找
-
用山脉数组特点可以看出,在峰值两侧的序列都是有序的:前半部分升序,后半部分降序(非常适合二分查找)
-
在对前后两部分进行二分查找前需要确定分界线即峰值位置下标
-
先根据nums[peak+1]<nums[peak]>nums[peak-1]找出峰值索引
-
在peak左侧二分查找target,peak右侧二分查找target,比较返回小下标
C/C++题解:
/*** class MountainArray {
* public:
* int get(int index);
* int length(); * };*/
class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int peak = binspeak(mountainArr);//peak下标索引
int leftval = binsltar(mountainArr,target,0,peak);
int rightval = binsrtar(mountainArr,target,peak,mountainArr.length()-1);
int res = leftval>rightval?rightval:leftval;//取下标较小的值
if(res==mountainArr.length()) return -1;//在数组中没有target返回-1
return res;}//否则返回较小下标
int binsltar(MountainArray &mountainArr, int target,int left,int right){
while(left <= right){//左侧二分查找target
int mid = (left + right)/2;//中间值
int val = mountainArr.get(mid);
if(val==target) return mid;
else if(val < target) left = mid + 1;
else right = mid - 1;}
return mountainArr.length();}
int binsrtar(MountainArray &mountainArr, int target,int left,int right){
while(left <= right){//右侧二分查找target
int mid = (left + right)/2;//中间值
int val = mountainArr.get(mid);
if(val==target) return mid;
else if(val < target) right = mid - 1;
else left = mid + 1;}
return mountainArr.length();}
int binspeak(MountainArray &mountainArr){//二分查找峰值下标
int left=0, right = mountainArr.length()-1;
while(left<=right){//由山峰数组知道peak是一定存在的
int mid =(left+right)/2;
int val = mountainArr.get(mid);
if (mid==0){//山峰比较倾斜,偏向左侧的时候注意边界
int val_r = mountainArr.get(mid+1);
if(val > val_r) return mid;
else left = mid + 1; }
else if(mid == mountainArr.length()-1){//峰偏向右侧的时候注意边界
int val_l = mountainArr.get(mid-1);
if(val > val_l) return mid;
else right = mid - 1; }
else{//中间位置可以直接get前后元素
int val_l = mountainArr.get(mid-1);
int val_r = mountainArr.get(mid+1);
if(val>val_l&&val>val_r) return mid;
else if(val>val_l&&val<val_r){
left = mid+1;}
else right=mid-1;}}
return -1;}};
Debug结果:
Python题解:
class Solution(object):
def findInMountainArray(self, target, mountain_arr):
""" :type target: integer:type mountain_arr: MountainArray
:rtype: integer"""
def binsltar(mountain_arr, target, left, right):
while(left <= right): #左侧二分查找target
mid = (left + right)/2 #中间值
val = mountain_arr.get(mid)
if(val==target): return mid
elif(val < target): left = mid + 1
else: right = mid - 1
return mountain_arr.length()
def binsrtar(mountain_arr, target, left, right):
while(left <= right): #右侧二分查找target
mid = (left + right)/2 #中间值
val = mountain_arr.get(mid)
if(val==target): return mid
elif(val < target): right = mid - 1
else: left = mid + 1
return mountain_arr.length()
def binspeak(mountain_arr): #二分查找峰值下标
left, right = 0, mountain_arr.length()-1
while(left<=right): #由山峰数组知道peak是一定存在的
mid =(left+right)/2
val = mountain_arr.get(mid)
if (mid==0): #山峰比较倾斜,偏向左侧的时候注意边界
val_r = mountain_arr.get(mid+1)
if(val > val_r): return mid
else: left = mid + 1
elif(mid == mountain_arr.length()-1): #峰偏向右侧的时候注意边界
val_l = mountain_arr.get(mid-1)
if(val > val_l): return mid
else: right = mid - 1
else: #中间位置可以直接get前后元素
val_l = mountain_arr.get(mid-1)
val_r = mountain_arr.get(mid+1)
if(val>val_l and val>val_r): return mid
elif(val>val_l and val<val_r):
left = mid+1
else: right=mid-1
return -1
peak = binspeak(mountain_arr) #peak下标索引
leftval = binsltar(mountain_arr,target,0,peak)
rightval = binsrtar(mountain_arr,target,peak,mountain_arr.length()-1)
res = min(leftval,rightval) #取下标较小的值
if(res==mountain_arr.length()): return -1 #在数组中没有target返回-1
return res #否则返回较小下标
Debug结果:
例题来自力扣网https://leetcode-cn.com/
当然,针对以上Java语言对前后两部分二分查找时可以直接调用Java本身封装的binarySearch()函数减少码量。
更多题解前往公众号即可全部免费获取