抵消

参考这里

题目已经规定一定会存在数量大于数组长度一半的数。

既然这个数一定存在，我们设之为$x$。我们将数字归为两类，一类就是$x$，一类是非$x$。我们统计这两种数的个数即可。

更进一步，我们并不关心这两种数字的准确数量，而只是关心这两个数字谁更多一点，然而我们并不清楚$x$到底是什么数。回想起经典的线性扫描求最值的做法–“擂台法”，同样的，一开始我们也不知道min到底是什么数。

min = 0
# 假设数组里全是正数
for x in list:
    if min > x:
        min = x

那么我们就采用“擂台”的方式，线性扫描数组，取一个数放上擂台。假如下一个数和擂台上的这个一样，那么我们说这个数离成为$x$更进了一步，count += 1假如下一个数和擂台上的不一样，那么就是离远了一步，count -= 1。当擂台上没人，count == 0，我们就把当前指向的数放上擂台，进行新一轮的$x$争霸。

线性扫描，时间复杂度$O(n)$，空间复杂度$O(1)$

class Solution(object):
    def moreThanHalfNum_Solution(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        plural, count = None, 0

        for x in nums:
            if not count:
                plural = x
                count += 1
                continue
            if plural != x:
                count -= 1
            else:
                count += 1

        return plural