数组中出现次数超过一半的数字

描述 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：0n≤50000，数组中元素的值 0≤val≤10000

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

输入描述： 保证数组输入非空，且保证有解

思路：可以排序，但是排序复杂度是O(nlogn)，空间复杂度也不会低，也可以遍历然后计数，如果次数大于数组长度的一半，则返回，时间、空间复杂度是O(n)。

最后一种解法是看评论得出的，评论大神牛，就是两两想消，最后剩下的就是结果。因为保证一定会有解，所以能坚持到最后的就是结果了

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        #解法一：哈希法
#         a = {}
#         for i in numbers:
#             if i in a:
#                 a[i] += 1
#             else:
#                 a[i] = 1
#             if a[i] > len(numbers) / 2:
#                 return i
        #解法二,相邻两个数若不同则消除，相同则计数
        result = numbers[0]
        count = 0
        for i in numbers:
            if count == 0:
                result = i
            if i == result:
                count += 1
            else:
                count -= 1
        return result