算法来查找数组中的三个多数元素

假设在非排序数组中有三个元素，所有元素都出现在元素总数的四分之一以上。算法来查找数组中的三个多数元素

找到这些元素的最有效方法是什么？对于这个问题的非在线和在线版本。

谢谢！

编辑

非网络版我指的是：这个数组中充分说明。在线版本意味着数组元素一次只有一个。

我需要的空间除了时间复杂性要紧。

免责声明：这不是家庭！我认为这是研究级别的问题。

2011-11-21 Qiang Li

听起来像功课。 – Cliff

什么是非在线版本的问题？ –

数组是排序的吗？ –

创建条目的直方图，对其进行排序，并取三个最大的条目。

2011-11-21 01:14:13 smitec

请记住最多三个元素和计数器。

记住第一元件，设置COUNT1 = 1
扫描，直至找到第一不同元件，增加COUNT1对于元件的每次出现1
记住第二elemt，设置COUNT2 = 1
扫描，直到找到与elem1和elem2不同的第一个元素，递增count1或count2，具体取决于您看到的元素
记住第三个元素，set count3 = 1
继续扫描，如果元素是其中一个元素如果没有记住的话，增加它的计数，减少所有三个计数;如果计数下降到0，则忘记该元素，转到步骤1,3或5，具体取决于您忘记了多少元素
如果您有三个元素严格超过四分之一的元素数数组中，最终会得到三个记忆元素，每个元素都有正数，这是三个多数元素。

小常量额外的空间，O（n），没有排序。

2011-11-21 01:46:28

+1。是的，这与我的思路不太一样。这是否泛化为长度为“n”的数组中的'm'元素，所有这些元素看起来都比'n/k'次多？ –

@QiangLi它概括为'm'元素出现超过'n /（m + 1）'次。但是如果我们将m作为变量，复杂度就是'O（m * n）'，所以如果m不小，排序就更好。 –

此算法不起作用 - 尝试按照序列元素排列：[1 2 3 4 4 1 5 5 2 6 6 3 1 1 2 2 3 3 3]。多数元素是1,2和3，而用这个算法你会发现非常不同的元素。 – ffriend

回答