题目

WeChat8530b986af8ca103e622d57d97f85686.png

我的思路

思路同 题目136
存入dict中，key存数字，value存counter。存完后，找到最大value的index并根据list(dict.keys())[index]找到对应的key。（这个方法以前有用到过）

  1. class Solution:
  2.     def majorityElement(self, nums: List[int]) -> int:
  3.         dict = {}
  4.         for num in nums:
  5.             if(num in dict):
  6.                 dict[num] += 1
  7.             else:
  8.                 dict[num] = 1
  9.         mode_count = max(list(dict.values()))
  10.         mode = list(dict.keys())[list(dict.values()).index(mode_count)]
  11.         return mode

Boyer-Moore Voting Algorithm

原理：因为众数出现数量超过一半，那么众数可以和其他数字出现次数相互抵消。同数counter + 1, 不同counter - 1, count = 0时重置当前众数。最后出现次数超半的众数一定会留下。

  1. class Solution:
  2.     def majorityElement(self, nums: List[int]) -> int:
  3.         mode = nums[0]
  4.         count = 1
  6.         for i in range(1, len(nums)):    
  7.             count = count + 1 if mode == nums[i] else count - 1           
  8.             if(count == 0):
  9.                 mode = nums[i]
  10.                 count = 1           
  11.         return mode