在数组中找到出现最频繁的元素

Question

你将得到一个长度不超过 2³² 的 32 位无符号整数数组，且数组中有超过一半的元素都相等于一个 32 位无符号整数 N。请找出 N，只遍历数组中的每个数字一次，并使用不超过 2 kB 的内存。

你的解决方案必须是确定性的，并保证能够找到 N。

- Jason Sundram

---

如果有人正在寻找流算法理论中这个经典问题的正确方法，请查看我的详细答案。 - Salvador Dali

Answer 1

为每个位保留一个整数，并适当地为数组中的每个整数递增此集合。

最后，某些位的计数将高于数组长度的一半 - 这些位确定了N。当然，计数将高于N出现的次数，但这并不重要。重要的是，任何不属于N的位不能出现超过一半的次数（因为N具有超过一半的条目），而任何属于N的位必须出现超过一半的次数（因为它将在每次N出现时出现，并且可能有额外出现）。

（目前没有代码 - 即将失去网络访问权限。希望上述内容足够清晰。）

- Jon Skeet

---

在读到你的答案之前，我并没有关心这个问题。Jon Skeet，我向你致敬。 - Ray

Boyer-Moore更好，但这个也很不错。 - Jonathan Graehl

@Toro：32个整数，每个大小为32位，再加上所需的任何本地变量。 - Jon Skeet

优美。然后你只需要取一个32位整数，通过新数组，如果元素i > orig_arr_len/2，则设置整数中相应的位，否则将其保持为0。 - user657862

你能区分“没有计数大于2^31的元素”和“计数大于2^31的元素为零”吗？ - Gabe

@Gabe：问题陈述中确实存在一个元素，其超过一半的元素都等于某个值。 - Jon Skeet

Answer 2

Boyer 和 Moore 的 “线性时间多数投票算法” - 在遍历数组时保持您对答案的当前猜测。

- buti-oxa

---

一种非常有趣的算法。与被接受的解决方案具有相同的复杂度，即O（n），但由于使用更少的数学运算，运行时间显着降低。 - Sparr

伟大的算法。我发现令人惊奇的是，1）我的一行代码完全描述了它，2）这个句子看起来像是第一次尝试编写的天真算法，一个不可能工作的尝试。 - buti-oxa

@buti-oxa 这个算法对于序列“A A A C C B B”有效吗？我无论如何都无法让它起作用。 - Pavan Dittakavi

@Pavan 不行，因为“数组中超过一半的条目等于N”的条件没有满足。 - buti-oxa

@buti-oxa 啊！这就解释了。谢谢你的回答 :) - Pavan Dittakavi

这太酷了。在阅读答案之前，我仔细思考了这个难题，并想出了上面那个计算位数的答案，认为自己相当聪明。然后，这个答案向我展示了我本可以有多聪明。 - Nathan Stretch

Answer 3

您只需要两个变量即可完成此操作。

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

将第一个数字设为嫌疑数字，然后继续循环列表。如果数字匹配，则增加嫌疑强度；如果不匹配，则降低嫌疑强度。如果嫌疑强度降至0，则当前数字成为嫌疑数字。这种方法不能找到最常见的数字，只能找到超过一半数量的数字。不要试图添加检查，判断是否大于列表长度的一半——它总是会导致更多的比较。

注意：我没有测试过这段代码，请自行决定是否使用。

- Jason Hernandez

Answer 4

Jon算法的伪代码（记事本C++ :-))：

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);

- Franci Penov

---

如果数组非常大，则使用算术运算和默认有符号整数类型可能会出现很多问题。 - Sparr

Answer 5

请注意，如果序列 a0, a1, . . . , an−1 包含一个领导者，则在删除两个不同值的元素后，剩余序列仍具有相同的领导者。事实上，如果我们删除两个不同的元素，则只有其中一个可能是领导者。新序列中的领导者出现次数大于 n/2 − 1 = (n−2)/2 次。因此，它仍然是具有 n − 2 个元素的新序列的领导者。

这是一个时间复杂度为 O(n) 的 Python 实现：

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader

- fatih tekin

Answer 6

这是流算法中的一个标准问题（其中你有一个巨大的（可能是无限的）数据流），并且你必须从该流中计算一些统计信息，只需通过该流一次即可。

---

显然，你可以使用哈希或排序的方法来处理它，但是对于可能无限的数据流，你会很快耗尽内存。因此，在这里你需要做一些聪明的事情。

---

大多数元素是指出现在数组大小的一半以上的元素。这意味着，大多数元素的发生次数比所有其他元素的发生次数加起来还要多；或者，如果您计算大多数元素的出现次数并减去所有其他元素的数量，则会得到一个正数。

因此，如果您计算某个元素的数量并减去所有其他元素的数量得到数字0，则原始元素不能是大多数元素。这是正确算法的基础:

使用两个变量（计数器和可能元素），迭代流。如果计数器为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)，其中常数非常小（比如 3）。此外，它的空间复杂度似乎是 O(1)，因为我们只初始化了三个变量。问题在于，这些变量中有一个是计数器，其可能会增长到 n（当数组由相同的数字组成时）。而要存储数字 n，需要 O(log (n)) 的空间。因此，从理论上讲，它的时间复杂度为 O(n)，空间复杂度为 O(log(n))。从实际角度来看，longint 可以容纳 2^128 个数字，而数组中的元素数量是不可想象的巨大。

另外请注意，该算法仅在存在多数元素时才有效。如果不存在这样的元素，它仍将返回一些数字，这肯定是错误的。（很容易修改算法以告知是否存在多数元素）

历史频道：这个算法是由 Boyer 和 Moore 在1982年发明的，被命名为Boyer-Moore 多数投票算法。

- Salvador Dali

Answer 7

我对这个算法有些记忆，它可能遵循2K规则，也可能不遵循。为了避免由于函数调用而破坏内存限制，可能需要使用堆栈等方式进行重写，但这可能是不必要的，因为它只有对数数量的这种调用。无论如何，我在大学时或者说有一个涉及分治的递归解决方案，其中的秘密是当你将组分成两半时，至少有一半仍然有超过一半的值等于最大值。在分割时的基本规则是返回两个候选的顶部值，其中一个是顶部值，另一个是其他值（可能是第二名，也可能不是）。我忘记了算法本身。

- Brian

Answer 8

针对buti-oxa / Jason Hernandez的答案，假设Jason的答案与buti-oxa的答案相同，并且两者都按照算法描述的方式工作，我们需要证明其正确性：

我们将调整后的怀疑强度定义为：如果选择了最高值，则等于怀疑强度；如果没有选择最高值，则为-怀疑强度。每次选择正确的数字时，当前的调整后怀疑强度增加1。每次选择错误的数字时，它要么减少1，要么增加1，具体取决于当前是否选择了错误的数字。因此，最小可能的结束时调整后怀疑强度等于number-of[top values] - number-of[other values]。

- Brian