image.png

思路：摩根投票法

  • 多支军队在打仗（或者联想投票也行），每轮出一个人（遍历nums），第一个人默认是候选人
  • 一轮出一个人，如果这个人和候选人是一方的（nums[i] == cur_candidate）,那么计数器num_candidates += 1
  • 如果这个人和候选人不一样，那么计数器减去1，需要注意的是，如果计数器变成0，需要执行两步操作：1.将候选人指定为新的人；2.原先数值为0的计数器增加1

    为什么不会被后面出现的数字捡漏？因为计数器一直在统计数量，后面出现的数字再怎么搞也无法超过总数的一半，所以无法捡漏。

代码：

  1. class Solution:
  2.     def majorityElement(self, nums: List[int]) -> int:
  3.         if not len(nums):
  4.             return 0
  5.         cur_candidate, num_candidates = nums[0], 0
  6.         for person in nums:
  7.             # 如果是同一方
  8.             if person == cur_candidate:
  9.                 num_candidates += 1
  10.             else:
  11.                 # 不是同一方就 -1
  12.                 num_candidates -= 1
  13.                 # 如果减到0了就换边
  14.                 if num_candidates == 0:
  15.                     cur_candidate = person
  16.                     # 此时的候选人数量也要 + 1
  17.                     num_candidates += 1
  19.         return cur_candidate

另外也有分治的办法，但是速度太慢了，所以我就没有写