算法：在一个圆环中找到峰值

Question

算法：在一个圆环中找到峰值

algorithmlanguage-agnosticgeometry

3

给定一个排列在圆形上的包含 n 个整数的序列，设计一种高效的算法来找到其中的一个峰值。峰值是指该数字不小于相邻两个数字。

一种方法是遍历所有整数，并检查每个整数是否为峰值。这样的时间复杂度为 O(n)。但似乎应该有一些分治的方法可以更加高效。

- Paul S.

需要知道圆中峰值的位置，还是只需要知道峰值的整数值？ - engineerC

需要位置和整数。假设整数存储为数组A[1..n]。 - Paul S.

请参见http://stackoverflow.com/questions/12867437/algorithm-find-peak-in-a-line。 - Matthew Strawbridge

那么一条平直的线就是峰顶了吗？3 3 3 3 3 3 => 没有任何一个元素比它的相邻元素小。 - Skizz

3个回答

2

这里是一个递归的O(log n)算法。

假设我们有一个数字数组，并且我们知道该段的中间数字不小于端点：

A[i] <= A[m] >= A[j]

对于数组中的i和j索引，m=(i+j)/2。检查位于端点和中点之间的元素，即索引为x=(3*i+j)/4和y=(i+3*j)/4的元素。如果A[x]>=A[m]，则在区间[i,m]上进行递归。如果A[y]>=A[m]，则在区间[m,j]上进行递归。否则，在区间[x,y]上进行递归。

在每种情况下，我们都保持上述区间的不变性。最终，我们会得到一个大小为2的区间，这意味着我们已经找到了峰值（它将是A[m]）。

要将圆形转换为数组，请取3个等距样本，并将自己定位到最大值（或与最大值并列）位于该区间的中间位置，而其他两个点则是端点。运行时间为O(log n)，因为每个区间的大小是前一个区间的一半。

我没有详细解释如何计算索引时如何舍入，但我认为你可以成功地解决这个问题。

- Keith Randall

0

当你说“按照圆形排列”时，你是指像循环链表一样吗？从你描述数据集的方式来看，这些整数是完全无序的，没有办法查看N个整数并对其他任何一个得出任何结论。如果是这种情况，那么暴力解决方案是唯一可能的。

编辑：

嗯，如果你不关心最坏情况下的时间，还有更高效的方法可以做到这一点。天真的方法是查看N_i、N_i-1和N_i+1是否为峰值，然后重复此过程，但你可以做得更好。

While not done
    If N[i] < N[i+1]
        i++
    Else
        If N[i]>N[i-1]
            Done
        Else
            i+=2

（嗯，不完全是这样，因为你必须处理N [i] = N [i + 1]的情况。但非常相似。）

这至少可以防止您将N _i与N _{i + 1}进行比较，将1添加到i，然后冗余地将N _i与N _i-1进行比较。虽然这只是微不足道的收益，但仍然在数字中前进，但没有办法绕过它;盲目跳跃是没有帮助的，而且没有办法提前查看，而不需要花费实际工作所需的时间。

- user1618143

6

这并不正确；如果你确定n_i大于n_(i+1)，就不需要检查n_(i+1)。可能并不需要检查所有的数字。这并不改变算法始终具有线性时间最坏情况的事实。 - Stephen Garle

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rob mayoff · Accepted Answer

编辑

好的，Keith Randall证明了我错了。 :)

这是Keith在Python中实现的解决方案：

def findPeak(aBase):
    N = len(aBase)
    def a(i): return aBase[i % N]

    i = 0
    j = N / 3
    k = (2 * N) / 3
    if a(j) >= a(i) and a(j) >= a(k)
        lo, candidate, hi = i, j, k
    elif a(k) >= a(j) and a(k) >= a(i):
        lo, candidate, hi = j, k, i + N
    else:
        lo, candidate, hi = k, i + N, j + N


    # Loop invariants:
    # a(lo) <= a(candidate)
    # a(hi) <= a(candidate)

    while lo < candidate - 1 or candidate < hi - 1:
        checkRight = True
        if lo < candidate - 1:
            mid = (lo + candidate) / 2
            if a(mid) >= a(candidate):
                hi = candidate
                candidate = mid
                checkRight = False
            else:
                lo = mid
        if checkRight and candidate < hi - 1:
            mid = (candidate + hi) / 2
            if a(mid) >= a(candidate):
                lo = candidate
                candidate = mid
            else:
                hi = mid

    return candidate % N