查找数组中最常见的条目

StackOverflow https://stackoverflow.com/questions/278488

题

给定一个 32 位无符号整数数组，长度最大为 232, ，对于某个 32 位无符号整数 N，具有数组中超过一半的条目等于 N 的属性。查找 N 只查看数组中的每个数字一次，并且最多使用 2 kB 内存。

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

有帮助吗？

解决方案

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

最后，一些位的计数将高于数组长度的一半 - 这些位确定为N.当然，计数将高于N出现的次数，但这不是物。重要的是，任何不属于N 的位都不能出现超过一半的次数（因为N有超过一半的条目），并且任何属于N 的位必须发生的次数超过一半（因为每次发生N时都会发生，以及任何额外的事件）。

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

其他提示

Boyer and Moore的“线性时间多数投票算法” ; - 沿阵列向下，保持你当前对答案的猜测。

只需两个变量就可以做到这一点。

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，则当前数字成为可疑数字。这将不找到最常见的数字，只有一个超过该组50％的数字。如果 suspicionStrength 大于列表长度的一半，则拒绝添加检查的冲动 - 它总是会导致更多的总比较。

P.S。我没有测试过这段代码 - 自己冒险使用它。

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);

请注意，如果序列 a0, a1, . . . , an−1 包含一个领导者，然后删​​除了一对不同值的元素，其余序列仍然具有相同的领导者。确实，如果我们删除两个不同的要素，那么其中只有一个可以成为领导者。新序列中的领导者比 n/2 − 1 = (n−2)/2次。因此，它仍然是新序列的领导者 n − 2 元素。

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

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

这是流式算法中的一个标准问题（你有一个巨大的（可能是无限的）数据流），你必须从这个流计算一些统计数据，一次通过这个流。

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

多数元素是发生超过数组大小一半的元素。这意味着多数元素的出现次数超过了所有其他元素的组合，或者如果你计算多数元素的次数，并且减去所有其他元素的数量，你将得到一个正数。

因此，如果计算某个元素的数量，并减去所有其他元素的数量并获得数字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（n），其常量非常小。此外，空间复杂度似乎是 O（1），因为我们只有三个变量初始化。问题是这些变量之一是一个可能长到 n 的计数器（当数组由相同的数字组成时）。要存储数字 n ，您需要 O（log（n））空间。所以从理论的角度来看它是 O（n）时间和 O（log（n））空间。 从实际开始，你可以在longint中输入2 ^ 128个数字，并且数组中的元素数量难以想象。

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

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

我对此算法有一些回忆，它可能会也可能不会遵循2K规则。它可能需要用堆栈等重写，以避免因函数调用而破坏内存限制，但这可能是不必要的，因为它只有这种调用的对数。无论如何，我对大学的模糊回忆或对此的递归解决方案涉及分而治之，秘诀是当你将组分成两半时，至少有一半的一半仍然有一半以上的值等于最大值。除法时的基本规则是返回两个候选顶值，其中一个是最高值，另一个是其他值（可能是也可能不是第二位）。我忘记了算法本身。

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

如果选择最高值，我们将调整后的怀疑强度定义为等于怀疑强度，或者如果未选择最高值，则将调整后的怀疑强度定义为-suspicion strength。每次选择正确的数字时，当前调整的怀疑强度增加1.每次选错号码时，它会下降1或增加1，具体取决于当前是否选择了错误的数字。因此，最小可能的结束调整后的怀疑强度等于[最高值]的数量 - [其他值]的数量

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top