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。需要帮助。

- Zeus

---

你没有从_find_peak函数中返回任何值，因此结果将始终为None。 - Daniel Roseman

最大的峰值？不可能。即使你只想找到任何一个峰值，在这个“峰值”的定义下，你也无法在O(log n)的时间内完成；只有当峰值被定义为任何元素至少与其相邻元素一样大时，才有可能。 - user2357112

抱歉，我修改了那行错误的代码。它不小心被忽略了。 - Zeus

在elif语句块中，您应该使用return _find_peak...。但仍然可能会得到不良结果（至少不是None）:) - Maroun

啊，我的错误，是peak而不是peek。 - alvas

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提供列表推导：

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

生成器表达式以类似的方式工作，但不会生成列表，而是生成迭代器，并且可以在不使用大量内存的情况下被消耗：

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

- Mike Müller

---

你能稍微解释一下这段代码吗？这已经超出了我的理解范围。 - Zeus

添加了一些解释。用例子和练习详细覆盖这些内容可以轻松地在一天内完成教学。 ;) - Mike Müller

Answer 2

我认为13也是峰值（大于12和8）。

尝试这种方法：

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


def find_peaks(arr):
    return list(_search(arr))


def _search(arr):
    last = len(arr) - 1
    for i, e in enumerate(arr):
        if not any((i > 0 and arr[i-1] > e, i < last and arr[i+1] > e)):
            yield e


if __name__ == '__main__':
    main()

如果你不明白任何东西，就问吧！

- Arĥimedeς ℳontegasppα ℭacilhας

Answer 3

另一种方法-仅使用一个函数：

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


def find_peaks(arr):
    last = len(arr) - 1
    return [
        e for i, e in enumerate(arr)
        if not any((i > 0 and arr[i-1] > e, i < last and arr[i+1] > e))
    ]


if __name__ == '__main__':
    main()

- Arĥimedeς ℳontegasppα ℭacilhας

---

如果您能解释一下您的方法，那真的会很有帮助。我在Python方面是一个彻头彻尾的新手。 - Zeus

[... for ...]句法是列表推导式：它在in后的可迭代对象的每次迭代中构建一个元素列表。enumerate()函数返回一个可迭代对象，其中每个元素都是包含元素索引（i）和元素本身（e）的元组。列表推导式中的if用于筛选元素：any()如果参数中任何元素为True，则返回True，因此它检查当前元素是否大于左侧（arr[i-1]）和右侧（arr[i+i]）邻居（既非左侧也不右侧的邻居更大）。 - Arĥimedeς ℳontegasppα ℭacilhας

换句话说：我只过滤原始的arr，仅选择不小于左边邻居且不小于右边邻居的元素（if not any(…)）。 - Arĥimedeς ℳontegasppα ℭacilhας

Answer 4

你漏掉了两个elif语句的返回值

- WindowsMaker

---

这并没有提供问题的答案。如果要批评或请求作者澄清，请在他们的帖子下留言。-【来自审查】 - Prune

@Prune，这回答了问题。它可能不是高质量的答案，但确实提供了一个答案。在审查时请更加小心。确保它实际上 不是 答案再将其标记为不是答案。 - Andy

根据我看到的SO准则，您应该提供正确的返回语句才能完全符合有效答案的要求。这是我的解释（包括我留下的一些简短答案），并不是SO惯例。 - Prune

Answer 5

我认为你无法在O(log N)时间内找到峰值，因为根据定义，项目不能按顺序排列，并且没有办法预测列表中任何项目的峰值性质，除非将项目N与项目N + 1进行比较，这可能是自反的 - 它告诉您N或N + 1可能是峰值。这会让您进行N/2次比较，然后必须跟随N/2次比较以检查峰值的另一侧。

这里有一个local_maxima(iterable)函数，您可以使用max()来查找峰值。如果起始/结束元素大于其一个邻居，则将其视为峰值。

data = [7, 12, 13, 8, 2, 16, 24, 11, 5, 1, None, 2, None, 3, 4, None, 5, 1, None]
firstpeak = [12, 7, 9, 8]
lastpeak = [1, 2, 3, 4]

def local_maxima(it):
    """Find local maxima in iterable _it_. Compares with None using
    `is (not) None`, and using operator `<`."""

    peaking = False
    last = None

    for item in it:

        # Deal with last item peaking
        if peaking and (item is None or item < last):
            yield last
            peaking = False
        elif item is None:
            peaking = False
        elif last is None or last < item:
            peaking = True
        else:
            peaking = False

        last = item

    if peaking:
        yield last

print([x for x in local_maxima(data)])
print("Highest:", max(local_maxima(data)))
print([x for x in local_maxima(firstpeak)])
print("Highest:", max(local_maxima(firstpeak)))
print([x for x in local_maxima(lastpeak)])
print("Highest:", max(local_maxima(lastpeak)))

- aghast