摩尔投票法

引入：主要元素

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。 输入：[1,2,5,9,5,9,5,5,5] 输出：5 输入：[3,2] 输出：-1

解：众所周知，主要元素最多只有 1 个。
摩尔投票法的核心就是比拼消耗。主要分为比拼消耗 paring 阶段和统计 counting 阶段。它基于这样一个事实：任意删除数组中两个不同的数，直至数组中不存在相同的数，那么剩下的数就是主要元素。
形象化理解：诸侯争霸游戏，假设你的人口占比超过总人口的一半，那么只要不内斗，每次和其他国家打仗都能一换一，最终赢家肯定是你。即使其他国家联合起来也打不过你，更不用说其他国家之间也会相互攻击。
算法过程：

  1. 遍历数组，从第一个元素开始计数，计数器初始为 1。
  2. 遇到与当前元素相同的元素时，计数器加 1，否则减 1（比拼消耗）。
  3. 若计数器为 0，则重新从当前元素开始计数，重复步骤 2 直至到达数组末尾（计数器为 0 表示前面所有的数都可以两两不同地比拼掉）。 ```go func majorityElement(nums []int) int { majority := pairing(nums) votes := counting(nums, majority) if votes <= len(nums) / 2 {
    1.  majority = -1
    } return majority }

func pairing(nums []int) int { majority, votes := -1, 0 for _, num := range nums { if votes == 0 { majority = num votes = 1 } else { if num == majority { votes++ } else { votes— } } } return majority }

func counting(nums []int, majority int) int { votes := 0 for _, num := range nums { if (num == majority) { votes++; } } return votes }

  1. paring 阶段必然返回数组中的一个众数，但是由于众数不止一个，所以还需要经过 counting 阶段确认是否存在主要元素。如果存在，那么 paring 阶段找到的众数必然是主要元素。
  3. <a name="97755670"></a>
  4. ### 算法分析：
  6. 1. 遍历两次 `nums` 数组，时间复杂度为 ![](https://g.yuque.com/gr/latex?O(n)#card=math&code=O%28n%29)。
  7. 1. 只定义了几个临时变量，时间复杂度为 ![](https://g.yuque.com/gr/latex?O(1)#card=math&code=O%281%29)。
  9. <a name="abtDN"></a>
  10. ## 推广：多个众数
  11. > 给定一个大小为 _n _的整数数组，找出其中所有出现超过 `⌊ n/3 ⌋` 次的元素。
  12. > 输入：[1,1,1,3,3,2,2,2]
  13. > 输出：[1,2]
  14. > 输入：nums = [1]
  15. > 输出：[1]
  17. 解：众所周知，这样的数最多有 2 个。<br />形象化理解：诸侯争霸游戏，当人口数占比超过总人口的 ![](https://cdn.nlark.com/yuque/__latex/7964c6a339acf2ddea25a5ef0552b97e.svg#card=math&code=%5Cfrac%7B1%7D%7B3%7D&height=37&width=14) 的国家不互相打仗而只与其他国家打仗，且其他国家之间也会相互打仗，每次打仗人口都是一换一，那么人口数占比超过总人口的 ![](https://cdn.nlark.com/yuque/__latex/7964c6a339acf2ddea25a5ef0552b97e.svg#card=math&code=%5Cfrac%7B1%7D%7B3%7D&height=37&width=14) 的国家必然是最终的赢家。
  18. ```go
  19. func majorityElement(nums []int) []int {
  20.     // 空数组
  21.     if len(nums) == 0 {
  22.         return []int{}
  23.     }
  24.     cand1, cand2 := pairing(nums)
  25.     vote1, vote2 := counting(nums, cand1, cand2)
  26.     var cands []int
  27.     if vote1 > len(nums) / 3 {
  28.         cands = append(cands, cand1)
  29.     }
  30.     if vote2 > len(nums) / 3 {
  31.         cands = append(cands, cand2)
  32.     }
  33.     return cands
  34. }
  36. func pairing(nums []int) (int, int) {
  37.     cand1, vote1 := nums[0], 0
  38.     cand2, vote2 := nums[0], 0
  39.     for _, num := range nums {
  40.         // 投给了第一位候选人
  41.         // 计票后直接结束，不抵消第二位候选人的票
  42.         if num == cand1 {
  43.             vote1++
  44.             continue
  45.         } 
  46.         // 投给了第二位候选人
  47.         // 计票后直接结束，不抵消第一位候选人的票
  48.         if num == cand2 {
  49.             vote2++
  50.             continue
  51.         } 
  52.         // 这一票没有投给当前的候选人
  53.         // 先看看当前是否有两位候选人
  54.         // 没有则找到匹配一个
  55.         if vote1 == 0 {
  56.             cand1 = num
  57.             vote1 = 1
  58.             continue
  59.         }
  60.         if vote2 == 0 {
  61.             cand2 = num
  62.             vote2 = 1
  63.             continue
  64.         }
  65.         // num != cand1 && num != cand2 && vote1 != 0 && vote2 != 0
  66.         // 说明当前已有两位候选人，但这一票没有投给他们两个中的一个
  67.         // 因此比拼消耗
  68.         vote1--
  69.         vote2--
  70.     }
  71.     return cand1, cand2
  72. }
  74. func counting(nums []int, cand1 int, cand2 int) (int, int) {
  75.     vote1, vote2 := 0, 0
  76.     for _, num := range nums {
  77.         if num == cand1 {
  78.             vote1++
  79.         } else if num == cand2 {
  80.             vote2++
  81.         }
  82.     }
  83.     return vote1, vote2
  84. }

算法分析：

  1. 遍历两次 nums 数组，时间复杂度为 摩尔投票法 - 图1#card=math&code=O%28n%29)。
  2. 只定义了几个临时变量，时间复杂度为 摩尔投票法 - 图2#card=math&code=O%281%29)。

    总结

    由此可见，摩尔投票法的应用是寻找**有特点的**众数。
    特点是：出现次数超过 摩尔投票法 - 图3 ，其中 摩尔投票法 - 图4