多数元素：不同票互相抵消
多数元素的个数比其余所有元素的个数之和还大。异值一对一消掉，消不完的那个就是它。
维护候选 candidate 和计数 count。count 为 0 时把当前值设为候选；当前值等于候选则 count++，否则 count--。多数元素出现次数大于 ⌊n/2⌋，抵消之后一定剩到最后。时间 O(n)，空间 O(1)。题目保证多数元素存在。
这是 LeetCode 169. Majority Element。大白话：数组长度为 n，找出出现次数大于 ⌊n/2⌋ 的那个元素。题目保证它一定存在，因此不必再扫一遍验证。
主例 nums = [2, 2, 1, 1, 1, 2, 2]。n=7，⌊n/2⌋=3，2 出现 4 次，1 出现 3 次，答案是 2。四个 2 比三个 1 多一个，这一个多出来的就是抵消后的剩余。
排序后取中间、哈希计数都能做对。进阶要 O(1) 空间。缺的不是「谁出现最多」这张表，而是一个只用两个变量就能把多数元素筛出来的不变量：不同值两两抵消，多数值消不完。
大于一半，不是恰好一半
多数元素的定义是严格大于 ⌊n/2⌋，不是 ≥。n=7 至少要 4 次。主例 2 出现 4 次刚好过线。题目保证存在，所以不会出现两个不同值都过线——两个过线加起来会超过 n。
这个「比其余总和还多」的数量关系，后面投票法直接当定理用。没有这个保证，投票法的候选可能是任意值，必须再扫一遍计数确认。
两条常规路：中点，或计数
排序之后，出现超过一半的值一定会盖住下标 n/2。主例排成 [1,1,1,2,2,2,2]，中间下标 3 是 2。无论 2 偏左还是偏右，长度超过一半的一段都会压住中点。时间 O(n log n)。
哈希表计每个值的次数，扫到某个次数 > n/2 就返回。时间 O(n)，空间 O(n)。两条都对，都没有用上「比其余总和还多」这笔数量，所以空间压不下去。
Boyer-Moore：同值加一，异值减一
只留两个变量：当前候选 candidate，以及它还没被抵消掉的票 count。规则三条。count 为 0，当前这个数成为新候选，count 从 1 起（代码里常写成先换候选再按是否相等加减，效果相同）。当前数等于候选，count++。当前数不等于候选，count--，相当于一对异值互相毁掉。count 掉到 0，旧候选被彻底抵消，下一格重新竞选。
为什么最后留下的一定是多数元素？把它和其余值做最坏配对：每一个其余值都可以干掉一个多数值。其余值总数 < n/2 < 多数值次数，所以多数值剩不下零。过程中候选可以换人——局部一段其余值抱团，会暂时把票仓打空——但全局多数值多出来的那些，最后还会把候选抢回来。
用手走主例，七帧和演示一一对应。下标 0：候选 2，票 1。下标 1：又一个 2，票 2。下标 2：1 来抵，票 1。下标 3：再一个 1，票 0。前四个 2,2,1,1 恰好两两消完。下标 4：票仓空，候选换成 1，票 1。下标 5：2 来抵，票 0。下标 6：票仓又空，候选换回 2，票 1。结束时候选是 2，majority 标在最后一帧。中间候选变成过 1，并不是错，那只是前缀被消完之后的局部竞选。
抵消票数超过一半，就不可能被其余值完全抵消。算法不统计真实次数，只维护「当前还没被消掉的差额」。本题保证存在，不必第二遍验证。
中间换候选，不推翻最后的 2
再看那两次归零。2,2,1,1 是两对异值，差额变成 0，候选作废，这是对的：就这四格而言没有多数。下一个 1 暂时当选，随即被 2 消掉，候选再次作废。最后只剩一个 2，它就是全局多出来的那一张。抵消不依赖顺序：把数组倒过来、打乱，只要 2 仍出现 4 次，最后候选仍是 2。
没有多数元素时，这套规则仍会吐出一个候选，只是那个值没有次数保证。本题不需要第二遍扫描；换成「可能不存在」的变体，必须再数一次 candidate 的真实出现次数。
八行 Go：投票算法
func majorityElement(nums []int) int {candidate, count := 0, 0for _, x := range nums {if count == 0 { candidate = x }if x == candidate { count++ } else { count-- }}return candidate}
1count==0 时先换候选。主例下标 4 换 1，下标 6 换回 2。
2换完立刻按是否相等加减。空仓遇上 x，会走 count++ 变成 1，不要先减。
3异值走 count--。主例下标 2、3、5 三拍都是这一支。
4返回 candidate。主例中间候选当过 1，返回值仍是最后的 2。
总结
同值加、异值减，票仓空了换候选。主例两次归零，最后仍是 2。
- 排序取中点 O(n log n)，哈希 O(n)/O(n)。O(1) 空间靠的是「多数比其余总和多」。
- 主例 2,2,1,1 消完，1 短暂当选，再被后面的 2 抢回。中间换候选不是 bug。
- 题目保证存在才可以不验证。可能不存在时必须再数一遍候选。