山脉数组中查找目标值

2020-04-29  本文已影响0人  我知他风雨兼程途径日暮不赏

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-in-mountain-array

1 题目

给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index,就请返回 -1。
何为山脉数组?如果数组 A 是一个山脉数组的话,那它满足如下条件:
首先,A.length >= 3
其次,在 0 < i < A.length - 1 条件下,存在 i 使得:

你将 不能直接访问该山脉数组,必须通过 MountainArray 接口来获取数据:
MountainArray.get(k) - 会返回数组中索引为k 的元素(下标从 0 开始)
MountainArray.length() - 会返回该数组的长度


/**
 * // 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 {
    public int findInMountainArray(int target, MountainArray mountainArr) {
      
    }
}

2 JAVA解答

首先二分法找出峰值,然后向峰值左侧进行二分查找等于target的值,如果无法找到向峰值右侧进行二分查找。


时间复杂度O(logN),空间复杂度O(1)
/**
 * // 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 {
    public int findInMountainArray(int target, MountainArray mountainArr) {
       int len = mountainArr.length();
       // 声明山峰值、山峰索引、二分法开始索引、二分法结束索引
       int max,mi,bi = 0,ei = len-1;
       int hi = (ei-bi)/2+bi;
        // 主程:二分法查找顶点坐标,mountainArr一定存在期望值,可以设置死循环
        while (true){
            int center = mountainArr.get(hi);
            int left = mountainArr.get(hi-1);
            int right = mountainArr.get(hi+1);
            if(center>left && center>right){
                max = center;
                break;
            }else if(center<left){
                ei = hi;
            }else if(center<right){
                bi = hi;
            }
            hi = (ei-bi)/2+bi;
        }
        mi = hi;
        if(target==max){
            return mi;
        }
        // 向左二分找target
        bi = 0;
        ei = mi-1;
        hi = (ei-bi)/2+bi;
        while (true){
            int mn = mountainArr.get(hi);
            if(mn==target){
                return hi;
            }else if(mn>target){
                ei = hi;
            }else {
                bi = hi;
            }
            hi = (ei-bi)/2+bi;
            if(hi==bi ||hi==ei){
                if(mountainArr.get(bi)==target){
                    return bi;
                }else if(mountainArr.get(ei)==target){
                    return ei;
                }else{
                    break;
                }
            }
        }
        // 向右二分
        bi = mi;
        ei = len-1;
        hi = (ei-bi)/2+bi;
        while (true){
            int mn = mountainArr.get(hi);
            if(mn==target){
                return hi;
            }else if(mn<target){
                ei = hi;
            }else {
                bi = hi;
            }
            hi = (ei-bi)/2+bi;
            if(hi==bi ||hi==ei){
                if(mountainArr.get(bi)==target){
                    return bi;
                }else if(mountainArr.get(ei)==target){
                    return ei;
                }else{
                    break;
                }
            }
        }
        return -1;
    }
}
上一篇下一篇

猜你喜欢

热点阅读