大小为n的数组，一个元素N / 2次 [英] Array of size n, with one element n/2 times

问题描述

由于n个整数数组，其中一个元素出现超过N / 2次。我们需要找到线性时间和不断的额外空间的元素。

Given an array of n integers, where one element appears more than n/2 times. We need to find that element in linear time and constant extra space.

YAAQ：另一个数组的问题

YAAQ: Yet another arrays question.

推荐答案

我有一个鬼鬼祟祟的怀疑它是沿东西线（在C＃）

I have a sneaking suspicion it's something along the lines of (in 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文件，礼貌博耶/摩尔的。）

It sounds unlikely to work, but it does. (Proof as a postscript file, courtesy of Boyer/Moore.)

这篇关于大小为n的数组，一个元素N / 2次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！