26

给定一个长度为 2 32的 32 位无符号整数数组，对于某些 32 位无符号整数 N，该数组中超过一半的条目等于 N。查找 N 查看每个数字在数组中只使用一次，最多使用 2 kB 的内存。

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

4

8 回答 8

61

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

最后，一些位的计数将高于数组长度的一半——这些位决定了 N。当然，计数将高于 N 发生的次数，但这没关系。重要的是，任何不属于 N 的位不能出现超过一半的次数（因为 N 有超过一半的条目）并且任何属于 N 的位必须出现超过一半的时间（因为它会发生每次出现 N 时，以及任何额外内容）。

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

于 2008-11-10T17:13:27.750 回答
43

Boyer 和 Moore 的“线性时间多数投票算法” ——沿着数组向下走，保持你当前对答案的猜测。

于 2008-11-10T18:22:16.860 回答
8

你可以只用两个变量来做到这一点。

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

将第一个数字设为可疑数字，然后继续循环遍历列表。如果数字匹配，则将怀疑强度增加一；如果不匹配，则将怀疑强度降低1。如果怀疑强度达到 0，则当前号码成为怀疑号码。这将无法找到最常见的数字，只能找到超过该组 50% 的数字。抵制添加检查是否suspicionStrength大于列表长度的一半的冲动 - 它总是会导致更多的总比较。

PS 我没有测试过这个代码 - 使用它需要您自担风险。

于 2008-11-11T02:55:45.170 回答
4

乔恩算法的伪代码（记事本 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);
于 2008-11-10T17:37:51.303 回答
2

请注意，如果序列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
于 2015-05-29T17:58:11.780 回答
2

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

显然，您可以通过散列或排序来处理它，但是对于潜在的无限流，您显然会耗尽内存。所以你必须在这里做一些聪明的事情。

多数元素是出现超过数组大小一半的元素。这意味着多数元素出现的次数比所有其他元素的总和还要多，或者如果您计算出现的次数，多数元素出现，然后减去所有其他元素的数量，您将得到一个正数。

因此，如果您计算某个元素的数量，并减去所有其他元素的数量并得到数字 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)之前的常数非常小O(n)（如 3）。看起来空间复杂度也是O(1)，因为我们只初始化了三个变量。问题是这些变量之一是一个计数器，它可能会增长到n（当数组包含相同的数字时）。并存储n您需要O(log (n))空间的号码。所以从理论的角度来看，它是O(n)时间和O(log(n))空间。从实际来看，您可以在一个 longint 中放入 2^128 个数字，而数组中的这个元素数量是难以想象的巨大。

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

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

于 2016-03-27T04:02:12.407 回答
0

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

于 2008-11-10T18:04:52.840 回答
0

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

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

于 2008-11-12T22:37:20.777 回答