题目：求众数

• 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。
• 你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

来源：力扣（LeetCode）第169题

链接：https://leetcode-cn.com/problems/majority-element

分析：

这道题很经典，方法有很多，暴力法，分治法，哈希法，排序法，随机法，投票法。我自己用了哈希法做出来的，但是官方的投票法真的是太秀了，这里着重讲投票法。

思路：

• 先让第一个人作为candidate，
• 然后和它一样的元素给他加票，不一样的元素给它减票，
• 当票数为0时，就换掉candidate，让新的元素担任。
• 最后成为candidate的元素就是众数。
• 当然，前提是题目给出地假设一定存在众数。

代码：

• 投票法：

  class Solution:
  def majorityElement(self, nums: List[int]) -> int:
      candidate = 0
      count = 0
      for num in nums:
          if count == 0:
              candidate = num
          count += 1 if num == candidate else -1
      return candidate
  

• 哈希法：(自己做的)

  class Solution:
  def majorityElement(self, nums: List[int]) -> int:
      cnt = len(nums) / 2
      dic = {}
      for num in nums:
          if num in dic:
              dic[num] += 1
          else:
              dic[num] = 1
          if dic[num] >= cnt:
              return num
  

复杂度分析：

• 投票法：
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)