大型营销型网站建设,jsp做的婚恋网站,wordpress网站下载文件,eclipse 制作网站开发1. 题目
给你一个 山脉数组 mountainArr#xff0c;请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index#xff0c;就请返回 -1。
何为山脉数组#xff1f;如果数组 A 是一个山脉数组的话#xff0c;那它满足如下…1. 题目
给你一个 山脉数组 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[i1] … 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() 100000 target 10^90 mountain_arr.get(index) 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-in-mountain-array 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先寻找最高点midmid1比较两者大小左边小l mid1右边小r mid然后先在左边二分查找找到了就返回没有的话继续查找右侧。
/*** // This is the MountainArrays 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 mArr) {int n mArr.length(), l 0, r n-1, high;int lval, rval, mid, midval, mid1, midval1;while(l r){mid l((r-l)1);midval mArr.get(mid);midval1 mArr.get(mid1);if(midval midval1)l mid1;elser mid;}high l;l 0; r high;while(l r){mid l((r-l)1);midval mArr.get(mid);if(midval target)return mid;else if(midval target)r mid-1;elsel mid1;}l high1, r n-1;while(l r){mid l((r-l)1);midval mArr.get(mid);if(midval target)return mid;else if(midval target)r mid-1;elsel mid1;}return -1;}
};4 ms 7.1 MB
