题解 | #数组中出现次数超过一半的数字#

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        # way 0
        lennumbers = len(numbers)
        if lennumbers == 0:
            return None
        numbers.sort()
        index = int(lennumbers / 2)
        count = 0
        for i in range(lennumbers):
            if numbers[i] == numbers[index]:
                count += 1
        if count > (lennumbers / 2):
            return numbers[index]
        return None

        # way 1
        # dict[key] = count
        numsdict = {}
        numlen = len(numbers)

        for num in numbers:
            if num in numsdict:
                numsdict[num] += 1
            else:
                numsdict[num] = 1
            if numsdict[num] > (numlen >> 1):
                return num
        return 0

        # way 2
        # 要想空间复杂度为O(1)，时间复杂度为O(n)
        # 遇到不相同的数字就相互抵消掉
        last = 0
        lastcount = 0
        for num in numbers:
            if lastcount == 0:
                last = num
                lastcount = 1
            else:
                if last == num:
                    lastcount += 1
                else:
                    lastcount -= 1
        if lastcount == 0:
            return 0
        else:
            lastcount = 0
            for num in numbers:
                if num == last:
                    lastcount += 1
            if lastcount > (len(numbers) >> 1):
                return last
        return 0