查找数组中最常见的项

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

最后,一些位的计数将超过数组长度的一半——这些位决定N。当然,计数将高于N出现的次数,但这并不重要。重要的是,任何不属于N的位 不能 出现超过一半的次数(因为N有超过一半的条目)和属于N的任何位 必须 发生的次数超过一半(因为它将在每次发生N以及任何额外的次数时发生)。

(目前没有代码-即将失去网络访问权限。不过,希望上面的内容足够清楚。)

Boyer and Moore's "Linear Time Majority Vote Algorithm"

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

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

努力寻找最常见的数字,只有一个数字,即超过50%的群体。如果需要,不要急于添加检查 suspicionStrength 大于列表长度的一半-它将始终导致更全面的比较。

另外,我还没有测试过这段代码——使用它的风险自负。

乔恩算法的伪代码(记事本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,那么你的原始元素就不能是多数元素。这是正确算法的基础:

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) O(1) ,因为我们只初始化了三个变量。问题是这些变量中有一个是计数器,它可能会增长到 n N 你需要 O(log (n)) 空间所以 从理论上看 它是 O(n) 时间和 O(log(n)) ,你可以在一个数组中放入2^128个元素,而数组中的元素数量是难以想象的巨大。

Boyer–Moore majority vote algorithm .

我记得这个算法,它可能遵循也可能不遵循2K规则。它可能需要使用堆栈等重写,以避免由于函数调用而打破内存限制,但这可能是不必要的,因为它只有对数数量的此类调用。不管怎么说,我对大学里的事情有模糊的回忆,或者对这个问题有一个递归的解决方案,涉及到分而治之,秘密是当你把这些组分成两半时,其中至少有一半的值仍然超过其最大值的一半。分而治之的基本规则是你返回两个候选的最高值,其中一个是最高值,另一个是其他值(可能是第二位,也可能不是第二位)。我忘记了算法本身。

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