1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 1095. 山脉数组中查找目标值

flypython • • leetcode题解

1095. 山脉数组中查找目标值

链接：https://leetcode-cn.com/problems/find-in-mountain-array/
难度：困难

题目

点击原文链接跳转查看题目

思路

这是一个以前没有遇到过的题目。不是说考点没遇到过，而是交互式这种题型。

题意中解释了什么是山脉数组，就是数组是先小到大后从大到小的，中间有个最大值。

现在是给一个target值，找到山脉数组中值最小的index。

和以前的那个翻转有序数组一样，这里也使用二分查找来解。

首先我们需要找到峰值，也就是最大值。因为本身他们就是两个单调递增和递减，找最大值也可以使用二分查找。那这里就会用三次二分查找。

最大值一次，左边找target，右边找target各一次。

至于交互式问题的写法，可以参考官方的例子，代码见解决方案。

方案代码

解决方案：

def binary_search(mountain, target, l, r, key=lambda x: x):
    target = key(target)
    while l <= r:
        mid = (l + r) // 2
        cur = key(mountain.get(mid))
        if cur == target:
            return mid
        elif cur < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        l, r = 0, mountain_arr.length() - 1
        while l < r:
            mid = (l + r) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                l = mid + 1
            else:
                r = mid
        peak = l
        index = binary_search(mountain_arr, target, 0, peak)
        if index != -1:
            return index
        index = binary_search(mountain_arr, target, peak + 1, mountain_arr.length() - 1, lambda x: -x)
        return index

原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/360.html

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 28/04/2020 11:07
下一篇 » 30/04/2020 11:10

相关推荐