众数，统计多数，摩尔投票，数位统计 - l00jj/algorithm GitHub Wiki
Boyer-Moore 投票算法（摩尔投票）
证明较难。简单说明如果我们把众数记为
+1，把其他数记为-1，将它们全部加起来，显然和大于0，从结果本身我们可以看出众数比其他数多。
具体实现:
- 维护一个候选众数
candidate和它出现的次数count。初始时candidate可以为任意值，count为0； - 遍历数组
nums中的所有元素，对于每个元素x，在判断x之前，如果count的值为0，我们先将x的值赋予candidate，随后我们判断x：- 如果
x与candidate相等，那么计数器count的值增加1； - 如果
x与candidate不等，那么计数器count的值减少1；
- 如果
- 在遍历完成后，
candidate即为整个数组的众数。
int candidate = 0, count = 0;
for (int i = left; i <= right; i++) {
if (sum == 0) {
candidate = arr[i];
count = 1;
} else {
if (arr[i] == candidate) count++;
else count--;
}
}
相关的变种和特性
摩尔投票可以分拆求解
对于一个连续的区域[head,tail]，取中间任意下标mid，对于[head,mid]与[mid,tail]进行摩尔投票，得出的结果res1 = [candidate1, count1]与res2 = [candidate2, count2]，两者可以进行合并，结果与[head,tail]的结果candidate相同，count不一定相同，但对判断具体哪个数是众数没有直接影响。根据此特性，可以结合线段树对给定区域预先进行分段预处理，能显著提升重复查询时的速度。
证明
- 在摩尔投票中，我们会存储两个值 (
num,cnt)，其中num表示答案，cnt表示num当前的价值。如果下一个数numNext=num，那么cnt的值加1，否则减1。当cnt变为-1时，会将num替换成numNext，并将cnt初始化为1； - 对于一个给定的数组，我们可以将它分成任意的两部分（即使不连续都可以），分别使用投票算法得到 (
num0,cnt0)和 (num1,cnt1)。那么整个数组使用投票算法得到的结果为：- 如果
num0=num1，结果为 (num0,cnt0+cnt1)； - 如果
num0≠num1，结果为cnt0和cnt1中较大的那个对应的num，以及|cnt0-cnt1|。
- 如果
我们可以使用通俗的解释证明正确性：投票算法本质上是在数组中不断找出两个不同的整数，把它们消除。当数组中只剩下一种整数时，这个整数就是num，它出现的次数就是cnt。如果数组中存在「绝对众数」，那么它就是num，否则最后剩下的num可能是任何值。因此，我们先将数组分成任意的两部分，分别进行消除，得到了cnt0个num0以及cnt1个num1。再将它们进行消除，就得到了整个数组进行投票算法的结果：
- 如果数组中存在「绝对众数」
num，那么根据鸽巢原理，一定有一个部分的绝对众数也是num，它可以在 (num0,cnt0) 或 (num1,cnt1) 中得到保留； - 如果不存在，那么 (
num0,cnt0) 和 (num1,cnt1)的值都无关紧要。
上述结合性可以推广到将数组拆分成任意多个部分的情形，因此我们就可以使用线段树，每个节点存储对应区间的 (num,cnt)。
例题：
1157. 子数组中占绝大多数的元素
对于每一次查询，我们可以对子数组先进行一次遍历，使用投票算法找出可能的「绝对众数」x′，再使用一次遍历，记录x′真正出现的次数，与threshold进行比较并得出答案。
这样做的时间复杂度为O(l)，其中l是子数组的长度，并不是一种高效率的做法。但我们可以发现，摩尔投票中存储的两个值是具有结合上述性质，可以通过线段树预存答案。
数位统计
通过记录当前范围内数字的二级制数位，把每一个二进制数位当做单独的记录点进行记录，在后续的查询中，把全部的数位进行查询，对符合查询结果的数位解析为1，不符合结果或没有的数位解析为0，最后将还原出来一个二进制数，在核实这个还原的二进制数是否存在即可。
例如在区域[head,tail]内有3个1，2个2，那么这个区域内在二进制0号位上共有3个点，1号位上有5个点，统计head<=mid<=tail上当前下标到head累计的点数，后面查询的时候对应还原出可能的bit即可。
例题：
class MajorityChecker:
bit = 1
idxs, arr, dicts = [], [], []
def __init__(self, arr: List[int]):
self.arr = arr
maxnum = max(arr)
while (1 << self.bit) <= maxnum: self.bit += 1
self.idxs = [None] * (maxnum + 1)
self.dicts = [[0] * (len(arr) + 1) for _ in range(self.bit)]
for i, num in enumerate(arr):
if self.idxs[num] == None: self.idxs[num] = []
self.idxs[num].append(i)
for j in range(self.bit):
self.dicts[j][i + 1] = self.dicts[j][i] + (num & 1)
num >>= 1
def query(self, left: int, right: int, threshold: int) -> int:
target = total = 0
lens = right - left + 1
for i in range(self.bit):
total = self.dicts[i][right + 1] - self.dicts[i][left]
if total >= threshold: target |= 1 << i
elif lens - total < threshold: return -1
arr = self.idxs[target]
if arr == None: return -1
if bisect_right(arr, right) - bisect_left(arr, left) < threshold: return -1
return target
排序统计
属于特定语言特定题解
例题1157. 子数组中占绝大多数的元素
统计每个数字出现的下标，排序这些数字，出现多的排在前面，查询的时候由多到少查询，剪枝超过阈值的情况
class MajorityChecker:
def __init__(self, arr: List[int]):
dic = defaultdict(list)
for i,num in enumerate(arr): dic[num].append(i)
self.dic = sorted(dic.items(), key=lambda it: -len(it[1]))
self.arr = arr
def query(self, left: int, right: int, threshold: int) -> int:
# 关键剪枝
if left + 1 == right:
return -1 if self.arr[left] != self.arr[right] else self.arr[left]
if left == right:
return self.arr[left]
for num, idxs in self.dic:
if len(idxs) < threshold: break
if bisect_right(idxs, right) - bisect_left(idxs, left) >= threshold: return num
return -1
获取众数方法
如何获取众数
方法一：哈希表
方法二：排序
前置条件，给定的数据内众数必然超过一半数量时排序法适用
方法三：随机化
前置条件，给定的数据内众数必然超过一定数量时随机法适用
方法四：分治
如果数
a是数组nums的众数，如果我们将nums分成两部分，那么a必定是至少一部分的众数。使用分治法解决这个问题：将数组分成左右两部分，分别求出左半部分的众数a1以及右半部分的众数a2，随后在a1和a2中选出正确的众数。具体实现时对于选出正确部分可以把对应区域扫描，扫描时直接统计两个候选树对应数量。
方法五：Boyer-Moore 投票算法（摩尔投票）
证明较难看上面链接。如果我们把众数记为
+1，把其他数记为-1，将它们全部加起来，显然和大于0，从结果本身我们可以看出众数比其他数多。