algorithm - 大小为 n 的数组，一个元素 n/2 次

Question

给定一个包含 n 个整数的数组，其中一个元素出现了 n/2 次以上。我们需要在线性时间和常量额外空间中找到该元素。

YAAQ:又一个数组问题。

Answer 1

我暗暗怀疑它与(在 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;
}

这听起来不太可能奏效，但确实如此。 (Proof as a postscript file，由博耶/摩尔提供。)