大小为n的数组,一个元素N / 2次 [英] Array of size n, with one element n/2 times
本文介绍了大小为n的数组,一个元素N / 2次的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
由于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屋!
查看全文