Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

题意

找出非空数组中的大多数元素，大多数是指出现次数大于1/2数组长度。

思路

1. 使用Counter函数，HashMap统计次数。
2. 摩尔投票：
   (1)对于nums，如果c此时为未知状态，则c=nums[i]，t=1，递增i。
   (2)如果c==nums[i]，++t，递增i。
   (3)如果c!=nums[i]，- -t，如果t==0，将c置为未知状态，递增i。
   所有投票处理完毕后，如果c为未知状态，则说明不存在任何候选人的得票数过半，否则重新遍历数组nums，统计候选人c的实际得票总数，如果c的得票数确实过半，则c就是最终结果。
   这个做法的原理就是既然有出现次数超过一半的数字，那么我们把没出现一半的数字的次数进行抵消，出现一半以上的数字仍然不会被完全消除掉。

from collections import Counter
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ele_dict =  Counter(nums)

        for e,c in ele_dict.items():
            if c > len(nums)//2:
                return e

class Solution:
    def majorityElement(self, nums):
        c = t = 0
        for num in nums:
            if c == num:
                t += 1
            elif c == 0:
                c = num
                t = 1
            else:
                t -= 1
        return c