大小为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;
}

听起来不太可行,但确实如此.(证明为后记文件,由Boyer/Moore提供.)

Answer 2

找到中位数,在未排序的数组上需要O(n).由于超过n/2个元素等于相同的值,因此中值也等于该值.