剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

 

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

输出: 2

我是用的字典存放的，速度比较慢。

之前也试过排序，但是有点寄。。

class Solution:

    def majorityElement(self, nums: List[int]) -> int:

        if not nums:return None

        dict={}

        totallen=len(nums)

        for i in range(totallen):

            if not nums[i] in dict:

                dict[nums[i]]=1

                if dict[nums[i]]>(totallen//2):

                    return nums[i]

            else:

                dict[nums[i]]+=1

                if dict[nums[i]]>(totallen//2):

                    return nums[i]

        return -1

然后用字典排序的话会快一点（返回第一个key搜了好久，呜呜呜我好菜啊，原来只要当成二维数组就行了）

然后dict的排序的话麻烦一点，用lambda表达式限定条件

x[1]表示按照value值排序，reverse表示从大带小排序。

看了看题解，还有摩尔排序法，搬过来~

若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。

class Solution:

    def majorityElement(self, nums: List[int]) -> int:

        votes = 0

        for num in nums:

            if votes == 0: x = num

            votes += 1 if num == x else -1

        return x