java - 选择算法以在 O(n) 中查找出现次数超过 n/2 的元素

Question

在不使用摩尔算法或哈希表的情况下，我需要找到数组中出现次数超过 n/2 的元素。

我知道我必须使用中位数中位数的选择算法。我对 select 算法返回什么感到困惑，因为如果它返回中位数，我如何确定该元素在数组中出现的次数超过 n/2 次？

例如:

a [] = {4, 1, 5, 7, 8}

5 是中位数，但它出现的次数不会超过 n/2 次。

现在:

a[] = {5, 5, 3, 4, 5, 5}

在这种情况下，中位数是 5，它出现了超过 n/2 次。

Answer 1

我想推荐另一种方法。这个问题被称为“寻找领导者”(至少在波兰文献中是这样)。让我们将出现次数超过 n/2 次的元素称为序列的首领。下面的观察是至关重要的——如果序列中存在一个领导者，在删除两个不同元素后，新创建的序列将具有与原始序列完全相同的领导者。这是为什么？如果有leader，去掉两个不同的元素后，恰好有一个是leader。新序列有 n - 2 个元素，并且超过 (n/2) - 1 次出现原始领导者，因此原始领导者是新领导者。您重复删除直到所有元素都相等。然后，您可以执行线性检查候选人是否是领导者。

示例代码(基于 this article ，遗憾的是没有英文版):

int leader = 0;
int number = 0; /* number of occurences of a leader candidate */
for (int k = 0; k < n; k++)
{
    if (number == 0)
    {
        //we set first element as a potential leader
        leader = a[k];
        number = 1;
    }
    else if (leader == a[k])
        //new leader occurence
        number++;
    else
        //delete two different elements
        number--;
}
//check if it really is the leader
number = 0;
for (int i = 0; i < n; i++)
    if (a[i] == leader)
        number++;
if (number > n / 2)
    System.out.println(leader);
else
    System.out.println("There is no leader");