当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.1095.Find in Mountain Array 山脉数组中查找目标值

LeetCode.1095.Find in Mountain Array 山脉数组中查找目标值

题目描述

1095 Find in Mountain Array
https://leetcode-cn.com/problems/find-in-mountain-array/

(这是一个 交互式问题 )

给你一个 山脉数组 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[i+1] > ... > A[A.length - 1]

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

注意:
对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外,任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
为了帮助大家更好地理解交互式问题,我们准备了一个样例 “答案”: https://leetcode-cn.com/playground/RKhe3ave , 请注意这 不是一个正确答案。

示例 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、先通过二分搜索找到峰值所在下标,二分的策略是如果 mid 位于左侧升序子数组上,则峰值肯定在 mid 右侧;相反,如果 mid 位于右侧降序子数组上,则峰值肯定在 mid 左侧
2、找到峰值下标后,先在左侧二分搜索
3、若左侧没有,在右侧二分搜索

看了题解后发现找峰值的二分搜索写的复杂了, 我比较了 mid 左右的元素,其实只需 mid 和他左侧(或右侧)的一个元素对比就行了

时间复杂度 O(logn),空间复杂度 O(1)

// 山脉数组接口
interface MountainArray {
    public int get(int index);
    public int length();
}

// 山脉数组实现类
class MyMountainArray implements MountainArray {
    private int[] array;

    MyMountainArray(int[] arr) {
        this.array = arr;
    }

    @Override
    public int get(int index) {
        return array[index];
    }

    @Override
    public int length() {
        return array.length;
    }
}

private static class SolutionV2020 {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        // 找峰值下标
        int peekIndex = findPeek(mountainArr);
        if (mountainArr.get(peekIndex) == target) {
            return peekIndex;
        }
        // 在峰值左侧升序序列中二分搜索
        if (peekIndex - 1 >= 0) {
            int leftRes = binarySearch(mountainArr, 0, peekIndex - 1, target, true);
            if (leftRes != -1) {
                return leftRes;
            }
        }
        // 在峰值右侧降序序列中二分搜索
        int length = mountainArr.length();
        if (peekIndex + 1 < length) {
            int rightRes = binarySearch(mountainArr, peekIndex + 1, length -1, target, false);
            return rightRes;
        }
        return -1;
    }

    // 二分搜索找山峰数组中峰值的下标
    private int findPeek(MountainArray mountainArr) {
        int length = mountainArr.length();
        int left = 0, right = length -1 ;
        while (left <= right) {
            if (right - left < 2) {
                return mountainArr.get(left) > mountainArr.get(right) ? left : right;
            }
            int mid = left + (right - left) / 2;
            int midValue = mountainArr.get(mid), midLeftValue = mountainArr.get(mid - 1), midRightValue = mountainArr.get(mid + 1);
            if (midValue > midLeftValue && midValue > midRightValue) {
                return mid;
            } else if (midValue > midLeftValue && midValue < midRightValue) {
                // mid在左升序序列中,则峰值在右侧
                left = mid + 1;
            } else {
                // mid在右降序序列中,则峰值在左侧
                right = mid - 1;
            }
        }
        return 0;
    }

    /**
     * 在有序数组 mountainArray[start...end] 中二分查找 target,找不到返回-1
     * @param mountainArray
     * @param start
     * @param end
     * @param target
     * @param asc true: 升序,false 降序
     * @return
     */
    private int binarySearch(MountainArray mountainArray, int start, int end, int target, boolean asc) {
        int left = start, right = end;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = mountainArray.get(mid);
            if (midValue == target) {
                return mid;
            } else if (midValue < target) {
                if (asc) {
                    left = mid + 1;
                } else {
                    right = mid -1;
                }
            } else {
                if (asc) {
                    right = mid -1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_1095_FindInMountainArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1095_FindInMountainArray.java


上一篇 LeetCode.202.Happy Number 快乐数

下一篇 LeetCode.剑指offer.056.数组中数字出现的次数

阅读
评论
946
阅读预计4分钟
创建日期 2020-04-29
修改日期 2020-04-29
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论