找到数组中的多数元素

Question

多数元素是发生超过数组大小一半的元素.

如何在数组中找到多数元素O(n)？

输入示例:

{2,1,2,3,4,2,1,2,2}

预期产量:

2

Answer 1

// returns -1 if there is no element that is the majority element, otherwise that element

// funda :: if there is a majority element in an array, say x, then it is okay to discard 
// a part of that array that has no majority element, the remaining array will still have
// x as the majority element

// worst case complexity :  O(n)

int findMajorityElement(int* arr, int size) { 
    int count = 0, i, majorityElement;
    for (i = 0; i < size; i++) {
        if (count == 0)
            majorityElement = arr[i];
        if (arr[i] == majorityElement) 
            count++;
        else
            count--;
    }
    count = 0;
    for (i = 0; i < size; i++)
        if (arr[i] == majorityElement)
            count++;
    if (count > size/2)
        return majorityElement;
    return -1;
}

Answer 2

令人遗憾的是,在5年内没有人为这个问题写过正确的解释.

这是流式算法中的标准问题(您有一个巨大的(可能无限的)数据流),您必须从此流计算一些统计信息,并通过此流一次.

显然,您可以使用散列或排序来处理它,但是如果有可能无限的流,您可以清楚地耗尽内存.所以你必须在这里做一些聪明的事情.

多数元素是发生超过数组大小一半的元素.这意味着多数元素的出现超过了所有其他元素的组合.也就是说,如果计算多数元素出现的次数,并减去所有其他元素的出现次数,您将得到一个正数.

因此,如果计算某个元素的出现次数,并减去所有其他元素的出现次数并得到数字0 - 那么原始元素不能是多数元素.这是正确算法的基础:

声明两个变量counter和possible_element.迭代流,如果计数器为0 - 你覆盖可能的元素并初始化计数器,如果数字与可能元素相同 - 增加计数器,否则减少它.Python代码:

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

很明显,算法O(n)之前的常数非常小O(n)(如3).它看起来像空间复杂度O(1),因为我们只有三个变量初始化.问题是这些变量之一是一个可能长大的计数器n(当数组由相同的数字组成时).并存储n您需要O(log (n))空间的数字.所以从理论的角度来看它是O(n)时间和O(log(n))空间.从实际情况来看,你可以在longint中拟合2 ^ 128个数字,并且数组中的这些元素数量难以想象.

另请注意,只有存在多数元素时,算法才有效.如果这样的元素不存在,它仍然会返回一些数字,这肯定是错误的.(很容易修改算法来判断多数元素是否存在)

历史频道:这个算法是1982年由Boyer,Moore发明的,并称为Boyer-Moore多数投票算法

Answer 3

多数元素(如果存在)也将是中位数.我们可以在O(n)中找到中位数,然后检查它确实是O(n)中的有效多数元素.更多实施链接的细节

Answer 4

多数元素:

大小为n的数组A []中的多数元素是一个出现超过n/2次的元素(因此最多只有一个这样的元素).

寻找候选人:

在O(n)中工作的第一阶段算法称为摩尔投票算法.算法的基本思想是,如果我们用e的所有其他元素抵消元素e的每次出现,那么如果它是多数元素,则e将存在直到结束.

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a)If a[maj_index] == a[i]
        count++
    (b)Else
        count--;
    (c)If count == 0
        maj_index = i;
        count = 1
3.  Return a[maj_index]

上面的算法循环遍历每个元素并保持[maj_index]的计数,如果下一个元素相同则增加计数,如果下一个元素不相同则减少计数,如果计数达到0则将maj_index更改为当前element和sets count为1. First Phase算法为我们提供了候选元素.在第二阶段,我们需要检查候选人是否真的是多数元素.

第二阶段很简单,可以在O(n)中轻松完成.我们只需要检查候选元素的数量是否大于n/2.

阅读geeksforgeeks了解更多详情