数组平衡点

Question

解决这个问题的最佳方法是什么？N元素阵列A的平衡点是索引i,使得较低索引上的所有元素具有值<= A [i],并且较高索引上的所有元素具有高于或等于A [i]的值.

例如,给定:

A [0] = 4 A [1] = 2 A [2] = 7 A [3] = 11 A [4] = 9

一个正确的解决方案是:2.A [2]以下的所有元素都小于A [2],A [2]之后的所有元素都大于A [2].在我看来,一个解决方案是O(nsquare)解决方案.有没有更好的解决方案？

Answer 1

首先假设A[0]是一个极点.然后开始走阵列; A[i]依次比较每个元素A[0],并跟踪当前的最大值.

一旦你找到了i这样的东西A[i] < A[0],你知道它A[0]不再是一个极点,并且通过扩展,任何元素都不能包括在内A[i].所以现在继续走,直到找到比当前最大值更大的下一个值.这就成了新提出的极点.

因此,O(n)解决方案!

在代码中:

int i_pole = 0;
int i_max  = 0;
bool have_pole = true;
for (int i = 1; i < N; i++)
{
    if (A[i] < A[i_pole])
    {
        have_pole = false;
    }
    if (A[i] > A[i_max])
    {
        i_max = i;
        if (!have_pole)
        {
            i_pole = i;
        }
        have_pole = true;
    }
}