https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm
https://leetcode.com/problems/online-majority-element-in-subarray/
这个算法是用来选择“一个序列中超过一半的元素”. 这个算法我很早在一本数据结构和算法的书中就学习到过， 但是作者给出的算法和BM算法真的一点都不像。所以我当时只是记住了怎么使用，但是没有深入理解这个算法有什么变形。
当时作者给出的算法是这样的：不断地消解两个连续的元素，如果他们一致就保留两个，否则全部丢弃。但是这个算法会对数组修改。
def majority_vote(a):
while len(a) != 1:
k = 0
for i in range(len(a), 2):
if a[i] == a[i+1]:
a[k] = a[i]
k += 1
if len(a) % 2 != 0:
a[k] = a[-1]
k += 1
if k == 0:
return None
a = a[:k]
return a[0]
print(majority_vote([1,2,1,1,2]))
print(majority_vote([1,2,1,1,2,2]))而wiki给出的BM算法更加简单，只需要维护几个变量就可以了。
- 假设我们先持有一个maj元素(P=None)和这个maj元素出现次数(C=0)
- 遍历整个序列(并且这个序列可以是streaming的)，假设当前元素是x
- 如果 C==0, 说明当前没有可选值，C=1, P=x.
- 如果 x==P, 那么 C++. 如果 x!=P, 那么 C–.
- 在结尾时，如果C>0的话，那么说明P就是majority元素.
def majority_vote(a):
p, c = None, 0
for x in a:
if c == 0:
p = x
c = 1
elif x == p:
c += 1
else:
c -= 1
if c == 0: return None
return p
print(majority_vote([1,2,1,1,2]))
print(majority_vote([1,2,1,1,2,2]))如果如果对第一个算法稍加改动，结合BM算法思想的话，就可以对任意区间求解majority.
我们将区间用区间树来表示，节点有两个值 `freq` （表示值出现频次）和 `value` (表示具体什么值). 我们在处理节点a, b的时候
- a.val == b.val => Tree(a.val, a.freq + b.freq)
- a.freq > b.freq => Tree(a.val, a.freq - b.freq)
- a.freq < b.freq => Tree(b.val, b.freq - a.freq)
只有当freq>0的话，val才是majority元素.
class SegTree:
def __init__(self):
self.val = self.freq = 0
self.left = self.right = None
self.start = self.end = 0
def bm_vote(a: SegTree, b: SegTree, c: SegTree):
if a.val == b.val:
c.val = a.val
c.freq = a.freq + b.freq
return
if b.freq < a.freq:
a, b = b, a
c.val = b.val
c.freq = b.freq - a.freq
return
def build_seg_tree(arr, s, e):
if s > e:
return None
if s == e:
t = SegTree()
t.val = arr[s]
t.freq = 1
t.start = s
t.end = e
return t
m = (s + e) // 2
left = build_seg_tree(arr, s, m)
right = build_seg_tree(arr, m + 1, e)
t = SegTree()
t.start = s
t.end = e
t.left = left
t.right = right
bm_vote(left, right, t)
return t
def query_seg_tree(t, s, e):
if s <= t.start and t.end <= e:
return t
m = (t.start + t.end) // 2
if (m + 1) > e:
# 只搜索左边
x = query_seg_tree(t.left, s, e)
elif m < s:
x = query_seg_tree(t.right, s, e)
else:
a = query_seg_tree(t.left, s, m)
b = query_seg_tree(t.right, m + 1, e)
x = SegTree()
bm_vote(a, b, x)
return x