algorithm - n个对象的等效测试

假设我们有一个“n”对象和一个子例程，它接受两个输入，并表示它们是否相等（例如，如果它们相等，它可以将输出作为1）。
我需要想出一个算法，调用上面的函数O（n logn）次，并决定输入是否有超过'n/2'个相互等价的项。

最佳答案

您可以使用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_most函数返回的值出现的次数这又增加了n个比较。