算法找到数组中的三大部分元素 [英] algorithm to find the three majority elements in an array

问题描述

让我们说有在非有序数组所有这些出现多于四分之一倍元素的总数的三个要素。

Let's say there are three elements in a non-sorted array all of which appear more than one-fourth times of the total number of elements.

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

What is the most efficient way to find these elements? Both for non-online and online versions of this question.

感谢您！

修改

非在线版本，我指的是：这个数组是完全指定。在线版本装置阵列元件来了一次一个。

The non-online version I was referring to is: this array is specified in full. The online version means the array elements are coming one at a time.

我需要除时间复杂度的空间紧张。

I require the space in addition to time complexity to be tight.

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

disclaimer: THIS IS NOT HOMEWORK! I consider this as research-level question.

推荐答案

记住多达三个要素，加上专柜。

Remember up to three elements, together with counters.

1. 记得第一个元素，设置COUNT1 = 1
2. 扫描，直到找到第一个不同的元素，增加COUNT1的元素1
每次出现
3. 记得第二elemt，设置COUNT2 = 1
4. 扫描，直到找到第一个元素，elem1和elem2时，递增COUNT1或COUNT2不同，这取决于哪一个元素，你看
5. 记得第三个元素，设置共3个记录= 1
6. 在继续扫描，如果该元素是记忆中的一个，增加它的数量，如果它没有任何记忆，减量所有三个罪名;如果计数下降到0，忘记该元素，返回步骤1，3，或5，取决于你有多少个元素忘了
7. 如果您有严格的发生超过四分之一的时间数组中元素的个数三个要素，你将最终有三个记得每个正数的元素，这些都是三大部分内容。

1. remember first element, set count1 = 1
2. scan until you find first different element, increasing count1 for each occurrence of element 1
3. remember second elemt, set count2 = 1
4. scan until you find first element different from elem1 and elem2, incrementing count1 or count2, depending which element you see
5. remember third element, set count3 = 1
6. continue scanning, if the element is one of the remembered, increment its count, if it's none of the remembered, decrement all three counts; if a count drops to 0, forget the element, go to step 1, 3, or 5, depending on how many elements you forget
7. If you have three elements occurring strictly more than one-fourth times the number of elements in the array, you will end up with three remembered elements each with positive count, these are the three majority elements.

小恒额外的空间，为O（n），不排序。

Small constant additional space, O(n), no sorting.

这篇关于算法找到数组中的三大部分元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！