python - Python 中的峰值查找器，复杂度为 O(log n)

Question

我是 Python 的新手，所以才有这个问题。我正在尝试解决一个标准的面试问题，即在数组中找到一个峰值。峰值被定义为大于其左右邻居的数字。我正在尝试找到最大的此类峰值。

这是我的代码:

def main():
    arr = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1]
    print(find_peak(arr))


def find_peak(arr):
    return _find_peak(arr, 0, len(arr))


def _find_peak(arr, start, stop):

    mid = (start + stop) // 2

    if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:
        return arr[mid]

    elif arr[mid] < arr[mid - 1]:
        _find_peak(arr, 0, mid - 1)

    elif arr[mid] < arr[mid + 1]:
        _find_peak(arr, mid + 1, stop)


if __name__ == '__main__':
    main()

该程序的输出是None，而预期的输出是24。任何帮助表示赞赏。

Answer 1

数据

arr = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1]

一行:

一行就够了:

max_peak = max(x2 for x1, x2, x3 in zip(arr, arr[1:], arr[2:]) if x1 < x2 > x3)

循环

当你刚接触 Python 时，可能更容易理解:

peak = float('-inf')
for x1, x2, x3 in zip(arr, arr[1:], arr[2:]):
    if x1 < x2 > x3:
        peak = max(peak, x2)
print(peak)

输出:

24

所有峰

您还可以使用单线获取所有峰值:

>>> [x2 for x1, x2, x3 in zip(arr, arr[1:], arr[2:]) if x1 < x2 > x3]
[13, 24]

并在结果上使用 max() 获得最大的一个。

解释

让我们看一下该解决方案的一些组件。我在这里使用 Python 3，每个人都应该这样做。 ;)

您可以对列表进行切片。

>>> arr = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1]

这为您提供了除第一个元素之外的所有列表:

>>> arr[1:]
[12, 13, 8, 2, 16, 24, 11, 5, 1]

这里从元素三开始:

>>> arr[2:]
[13, 8, 2, 16, 24, 11, 5, 1]

zip()函数将多个序列压缩在一起。要可视化发生的情况，您可以将 zip 对象转换为列表:

>>> list(zip(arr, arr[1:], arr[2:]))
[(7, 12, 13),
 (12, 13, 8),
 (13, 8, 2),
 (8, 2, 16),
 (2, 16, 24),
 (16, 24, 11),
 (24, 11, 5),
 (11, 5, 1)]

Python 支持元组解包。这允许为元组的所有成员分配单独的名称:

>>> x1, x2, x3 = (7, 12, 13)
>>> x1
7
>>> x2
12
>>> x3
13

另一个不错的功能是比较两个以上的对象:

>>> 10 < 12 > 8
True

这相当于:

>>> (10 < 12) and (12 > 8)
True

Python 提供 list comprehensions :

>>> [x * 2 for x in range(2, 6)]
[4, 6, 8, 10]

Generator expression以类似的方式工作，但不生成列表，而是生成迭代器，并且可以在不使用大量内存的情况下使用:

>>> sum(x * 2 for x in range(2, 6))
28