算法：寻找峰转了一圈 [英] Algorithm: Find peak in a circle

问题描述

由于 N 整数，排成一个圆圈，显示出高效的算法，可以找到一个高峰。峰值是一个数字，并不比两个数字少旁边。

Given n integers, arranged in a circle, show an efficient algorithm that can find one peak. A peak is a number that is not less than the two numbers next to it.

一种方法是通过所有的整数和检查每个人看到它是否是一个高峰。国债收益率 O（N）的时间。好像应该有某种方式来分而治之更有效率，但。

One way is to go through all the integers and check each one to see whether it is a peak. That yields O(n) time. It seems like there should be some way to divide and conquer to be more efficient though.

推荐答案

下面是一个递归 O（log n）的算法。

假设我们有数字数组，而我们知道，该段的中间数不大于端点小

Suppose we have an array of numbers, and we know that the middle number of that segment is no smaller than the endpoints:

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

对于I，J指标到一个数组，而 M =（I + J）/ 2 。检查中途端点和中点之间的所有元素，即那些在指数 X =（3 * I + J）/ 4 和 Y =（我+ 3 * j）条/ 4 。如果 A [X]＆GT; = A [M] ，然后递归的间隔 [I，M] 。如果 A [Y]＆GT; = A [M] ，然后递归的间隔 [M，J] 。否则，递归在区间 [X，Y] 。

for i,j indexes into an array, and m=(i+j)/2. Examine the elements midway between the endpoints and the midpoint, i.e. those at indexes x=(3*i+j)/4 and y=(i+3*j)/4. If A[x]>=A[m], then recurse on the interval [i,m]. If A[y]>=A[m], then recurse on the interval [m,j]. Otherwise, recurse on the interval [x,y].

在每一种情况下，我们维持上面的间隔不变。最终我们得到大小为2的区间，这意味着我们已经找到了一个峰值（即 A [M] ）。

In every case, we maintain the invariant on the interval above. Eventually we get to an interval of size 2 which means we've found a peak (which will be A[m]).

要圆转换为一个阵列，取3等距​​离的样品和确定自己的方位，以使最大（或一个并列最大）为在区间的中部，另两个点的端点。运行时间为 O（log n）的，因为每个间隔的previous一半大小。

To convert the circle to an array, take 3 equidistant samples and orient yourself so that the largest (or one tied for the largest) is in the middle of the interval and the other two points are the endpoints. The running time is O(log n) because each interval is half the size of the previous one.

我已经掩盖了如何计算索引时四舍五入问题，但我认为你可以工作了这一点成功。

I've glossed over the problem of how to round when computing the indexes, but I think you could work that out successfully.

这篇关于算法：寻找峰转了一圈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！