查找主要元素出现次数超过n/3次

Question

下面的算法拼图工作和下面的解决方案调试工作，为几个测试用例。我的困惑和问题是，我们怎么能总是保证一个元素的计数出现超过n/3次都是正计数？还有其他2n/3元素可以使它计数为负数？但我试过了，它在我的样品中总是有效的。如果有人能帮忙澄清，那就太好了。在

这里是我的陈述和测试代码

给定一个大小为n的整数数组，找出出现次数超过⌊n/3⌋次的所有元素。该算法应在线性时间和O（1）空间中运行。在

def majorityElement(nums):
    if not nums:
        return []
    count1, count2, candidate1, candidate2 = 0, 0, 0, 0
    for n in nums:
        if n == candidate1:
            count1 += 1
        elif n == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = n, 1
        elif count2 == 0:
            candidate2, count2 = n, 1
        else:
            count1, count2 = count1 - 1, count2 - 1
    return [n for n in (candidate1, candidate2) if nums.count(n) > len(nums) // 3]

if __name__ == "__main__":

    # print majorityElement([1,2,1,3,1,5,6])
    print majorityElement([2,3,1,2,1,3,1,5,5,1,6])

提前谢谢你， 林

Answer 1

从概念上讲，我们反复对列表应用一个缩减操作，该操作涉及删除三个成对不同的项。这个特定的代码在网上进行了缩减，因此到目前为止，缩减后的列表可以用两个不同的元素及其对应的计数来描述（因为如果有第三个元素不同于其他两个元素，那么我们可以减少）。最后，对于发生次数超过n/3的情况，我们最多考虑两个因素。在

正确性证明中有趣的部分是一个引理，每当我们执行这个简化操作时，任何在旧列表中出现n/3次以上的元素在新列表中出现的次数都多于n'/3次，其中n是旧列表的长度，n'=n-3是新列表的长度。这通过归纳确保最终列表包含在初始列表中出现超过n/3次的所有元素（当然，最终列表只包含两个不同的元素）。在

引理的证明是，如果一个项在旧列表中的n次出现k次，那么在最坏的情况下，它在新列表中的n-3次中出现k-1次，如果k/n>；1/3，则

              (k-1) n
(k-1)/(n-3) =    -
              (n-3) n

              k (n-3) + 3 k - n
            =         -
                   (n-3) n

                      (k/n - 1/3)
            = k/n + 3      -
                          n-3

            > 1/3.