2

给定n整数，排列成一个圆圈，显示一种可以找到一个峰值的有效算法。一个峰值是一个不小于它旁边的两个数字的数字。

一种方法是遍历所有整数并检查每个整数以查看它是否是峰值。这就产生O(n)了时间。似乎应该有一些方法来分而治之，以提高效率。

4

3 回答 3

3

编辑

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

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

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
于 2012-10-12T21:05:07.853 回答
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)因为每个间隔都是前一个间隔大小的一半。

我已经掩盖了计算索引时如何舍入的问题，但我认为你可以成功地解决这个问题。

于 2012-10-12T21:56:28.997 回答
0

当你说“排列成一个圆圈”时，你的意思是像一个循环链表还是什么？从您描述数据集的方式来看，听起来这些整数是完全无序的，没有办法查看 N 个整数并得出关于其他任何整数的任何结论。如果是这种情况，那么蛮力解决方案是唯一可能的解决方案。

编辑：

好吧，如果您不关心最坏情况的时间，那么有一些更有效的方法可以做到这一点。天真的方法是查看 N i、 N i-1和 N i+1以查看 Ni 是否是一个峰值，然后重复，但你可以做得更好。

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进行冗余比较。不过，这是一个明显的边际收益。你仍然在通过数字前进，但没有办法解决这个问题；盲目地跳跃是没有帮助的，如果不花时间做实际的工作，就没有办法展望未来。

于 2012-10-12T21:04:22.053 回答