大小为 n 的数组，其中一个元素 n/2 次

给定一个由 n 个整数组成的数组，其中一个元素出现超过 n/2 次。我们需要在线性时间和恒定的额外空间中找到该元素。

YAAQ：又一个数组问题。

我有一种偷偷的怀疑，这类似于（在 C# 中）

// We don't need an array
public int FindMostFrequentElement(IEnumerable<int> sequence)
{
    // Initial value is irrelevant if sequence is non-empty,
    // but keeps compiler happy.
    int best = 0; 
    int count = 0;

    foreach (int element in sequence)
    {
        if (count == 0)
        {
            best = element;
            count = 1;
        }
        else
        {
            // Vote current choice up or down
            count += (best == element) ? 1 : -1;
        }
    }
    return best;
}

这听起来不太可能起作用，但确实有效。 （证明作为 postscript 文件 http://www.cs.utexas.edu/users/boyer/mjrty.ps.Z，由博耶/摩尔提供。）