algorithm - 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 个比较。