c++出现次数超过一半的数

摩尔投票法（Moore Voting Algorithm）可以解决出现次数超过一半的数的问题。

算法思路：

1. 选取第一个数字作为候选数candidate，计数器count初始化为1。
2. 从第二个数字开始遍历数组，如果当前数字与candidate相同，则计数器count加1，否则计数器count减1。
3. 如果计数器count变为0，则将candidate更新为当前数字，并将计数器count重新设置为1。
4. 遍历结束后，candidate就是出现次数超过一半的数。

证明：

假设存在一个数x出现次数超过一半，那么x的出现次数大于其他所有数出现次数之和。在遍历数组的过程中，当遇到一个与x不同的数时，计数器count减1，当遇到一个与x相同的数时，计数器count加1。由于x的出现次数大于其他所有数出现次数之和，所以在遍历完整个数组之后，计数器count一定大于0。因此，candidate就是x。

代码实现：

时间复杂度：O(n)
空间复杂度：O(1)

def majorityElement(nums):
    candidate = nums[0]
    count = 1
    for i in range(1, len(nums)):
        if nums[i] == candidate:
            count += 1
        else:
            count -= 1
            if count == 0:
                candidate = nums[i]
                count = 1
    return candidate