n个对象的等价测试

Question

假设我们有“n”个对象和一个子例程，该子例程接受两个输入并判断它们是否相等（例如，如果它们相等，它可以给出输出 1）。

我需要提出一种算法，该算法调用上述函数 O(n log n) 次，并确定输入是否具有超过“n/2”个彼此等效的项。

Answer 1

您可以使用 Boyer-Moore 多数投票算法，该算法最多进行 n-1 次比较。

function find_majority(A)
    majority = None
    count = 0
    for a in A:
        if count == 0
            majority = a
        else if a == majority
            count += 1
        else
            count -= 1
    return majority

如果在数组中出现超过 n/2 次，则返回最常见的元素。

如果您需要知道是否存在多数项，则可以第二次遍历数组，计算 find_majority 函数返回的值出现的次数。这又增加了n次比较。