Boyer Moore Majority Vote Algorithm

题目

MajorityElementII
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

• Example 1:

  Input: [3,2,3]
  Output: [3]

• Example 2:

  Input: [1,1,1,3,3,2,2,2]
  Output: [1,2]

解题报告

理解题意

• 给定一个数组，大小为 n，让找到所有出现多于⌊ n/3 ⌋ 次的元素
• 题目要求线性时间，以及 O(1) 的空间复杂度

Boyer-Moore majority vote algorithm

该算法来自一篇论文Boyer-Moore Majority Vote Algorithm，运行时间为O(n)，空间复杂度为O(1)，他只要求对输入遍历两次。虽然实现起来比较简单，但是理解起来还是需要花点时间。

• 第一遍

  1. 我们需要定义两个变量：candidate 和 count
  2. 对于每一个输入的元素，首先看 count，如果 count 为 0，将当前位置元素赋给 candidate
  3. 比较当前位置的元素 与 candidate，如果相等：count+1，如果不等 count-1
     说白了，就是不一样的就可以抵消一个，最后剩下的 candidate 就是候选，最后在确认一次即可。

candidate = 0
count = 0
for value in input:
    if count == 0:
        candidate = value
    if candidate == value:
        count += 1
    else:
        count -= 1

当执行完毕后，candidate 即为 majority value 如果存在的话。

• 第二遍
  确定一下 candidate 是不是 majority 元素。