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

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

知识点：

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

采用阵地攻守的思想： 设置士兵soldier（初始时为第一个元素）,士兵当前生命值soldierCount（每次的初始值为0），当前士兵对应的数组下标soldierIndex（起始值为0），对数组进行遍历，如果soldier与当前元素相等，则soldierCount加一，否则soldierCount减一，如果soldierCount为0，则soldierIndex增一即更新soldier的值，到最后如果soldierCount为1，则此时soldier可能为出现次数超过一半的元素，之所以可能是因为存在一种情况比如：[1,2,3]，这样遍历到最后一个元素时soldier为3对应的soldierCount最后的值也是1而非0因为其初始值为1，没增也没减，解决方法是增加一个flag用来标记当前soldierCount是否增加过，如果当前soldierCount增加过但是后来由于减1减到了1则当前soldier就是出现次数超过一半的元素，否则不是。

代码

    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if numbers is None:
            return 0

        size = len(numbers)

        if size == 0:
            return 0
        if size == 1:
            return numbers

        soldier = numbers[0]
        soldierCount = 1
        soldierIndex = 0
        flag = False
        for i in range(1, size):
            if numbers[i] != soldier:
                soldierCount -= 1
                if soldierCount == 0:
                    soldierIndex += 1
                    soldier = numbers[soldierIndex]
                    soldierCount = 1
                    flag = False
            else:
                flag = True
                soldierCount += 1

        if soldierCount > 1:
            return soldier
        elif soldierCount == 1 and flag:
            return soldier
        else:
            return 0

这里