维基百科

    背景：找出一组数字序列中出线次数大于总数 1/2 的数字（并假设一定存在这个数字）。显然这个数字只存在一个。

    每次从序列出选择两个不相同的数字删掉（或者是“抵消”），最后剩下的一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

    中心思想就是：删除，删除，删除，直到不能删除为止。

    维护两个变量，分别是最后的结果 res 和计数值 count ，其实这俩变量表达的是一个隐形的数组，数组中存储的是 当前暂时无法删除的数字 也就是 res ， count 表示数组的长度

    伪代码

    • 初始化元素m并给计数器i赋初值i = 0
    • 对于输入队列中每一个元素x：
      • 若i = 0, 那么 m = x and i = 1
      • 否则若m = x, 那么 i = i + 1
      • 否则 i = i − 1
    • 返回 m

    举个栗子

    1. 输入 {1,2,1,3,1,1,2,1,5}
    2. res = 0 count = 0
    4. 第1步：没有元素可以跟当前的结果抵消
    5. 当前值 curr 为 1，，count == 0 ，所以 res = curr(1)，count++(1)
    7. 第2步：当前值 curr 为 2，当前值不等于 res，所以抵消掉当前结果，可以暂时不修改res 的结果
    8. count != 0 && res != curr，所以 res 保持不变(1), count--(0)
    10. 第3步：当前值 curr 为 1，count == 0， 当前值不等于 res，所以抵消掉当前结果，可以暂时不修改res 的结果
    11. count == 0，所以 res = curr(1), count++(1)
    13. 第4步：当前值 curr 为 3， count != 0 && res != curr, 所以 res 保持不变(1), count--(0)
    15. 第5步：当前值 curr 为 1， count == 0, 所以 res = 1, count++(1)
    17. 第6步：当前值 curr 为 1， count == 0 ,所以 res = curr(1)，count++(2)
    19. 第7步：当前值 curr 为 2， count != 0 && res != curr, 所以 res 保持不变(1),count--(1)
    21. 第8步：当前值 curr 为 1， count == 0, 所以 res = curr(1),count++(2)
    23. 第9步：当前值 curr 为 5， count != 0 && res != curr, 所以 res 保持不变(1)，count--(1)

    超过 1/3 的 众数

    1. package main
    3. // @lc code=start
    4. func majorityElement(nums []int) []int {
    5.     target := len(nums) / 3
    6.     cur1, cur2 := 0, 0
    7.     count1, count2 := 0, 0
    9.     for _, val := range nums {
    10.         if cur1 == val && count1 > 0 {
    11.             count1++
    12.         } else if cur2 == val && count2 > 0 {
    13.             count2++
    14.         } else if count1 == 0 {
    15.             cur1 = val
    16.             count1++
    17.         } else if count2 == 0 {
    18.             cur2 = val
    19.             count2++
    20.         } else {
    21.             count1--
    22.             count2--
    23.         }
    24.     }
    25.     count1, count2 = 0, 0
    26.     for _, val := range nums {
    27.         if val == cur1 {
    28.             count1++
    29.         } else if val == cur2 {
    30.             count2++
    31.         }
    32.     }
    33.     res := make([]int, 0)
    34.     if count1 > target {
    35.         res = append(res, cur1)
    36.     }
    37.     if count2 > target {
    38.         res = append(res, cur2)
    39.     }
    40.     return res
    41. }