多数元素
Boyer-Moore 投票 · 候选人/票数抵消 · 空间 O(1)可视化:哈希表nums=[2,2,1,1,1,2,2],找出出现次数超过 ⌊n/2⌋ 的多数元素,答案是 2。直觉:多数元素出现次数超过一半,比其他所有元素加起来还多。
最直观:数一遍每个值出现几次
nums=[2,2,1,1,1,2,2],找出出现次数超过 ⌊n/2⌋ 的多数元素,答案是 2。直觉:多数元素出现次数超过一半,比其他所有元素加起来还多。
candidate(候选人)、count(净票数)、current(当前值)、index(下标)。
维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。
count 始终等于当前 candidate 在「还没被抵消」的元素里的净票数;count 归零代表前面这一段已两两抵消干净。
这题最直观可以用哈希表统计频次，时间 O(n)、空间 O(n)。更优解是 Boyer-Moore 投票法：维护 candidate 和 count。遇到相同元素 count++，遇到不同元素 count--，count 为 0 时更换候选人。因为多数元素出现次数超过一半，它和其他元素抵消后仍会剩下，所以最终 candidate 就是多数元素。时间 O(n)，空间 O(1)。
nums=[2,2,1,1,1,2,2],找出出现次数超过 ⌊n/2⌋ 的多数元素,答案是 2。直觉:多数元素出现次数超过一半,比其他所有元素加起来还多。
维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。
candidate(候选人)、count(净票数)、current(当前值)、index(下标)。
扫描 [2,2,1,1,1,2,2],投票抵消后 candidate=2,返回 2。
- · count 始终等于当前 candidate 在「还没被抵消」的元素里的净票数;count 归零代表前面这一段已两两抵消干净。
- · 多数元素出现次数 > ⌊n/2⌋,和其他所有元素一一抵消后仍有剩余。
- · count 不是 candidate 的真实出现次数，而是抵消后的净票数。
- · candidate 中途变化是正常的，不代表算法出错。
- · 如果题目不保证多数元素存在，需要最后再扫描一遍验证 candidate 的真实次数。
- · 阈值是「严格大于 ⌊n/2⌋」,不是「大于等于」。
- · LC229 多数元素 II
- · LC347 前 K 个高频元素
- · LC217 存在重复元素
这题最直观可以用哈希表统计频次，时间 O(n)、空间 O(n)。更优解是 Boyer-Moore 投票法：维护 candidate 和 count。遇到相同元素 count++，遇到不同元素 count--，count 为 0 时更换候选人。因为多数元素出现次数超过一半，它和其他元素抵消后仍会剩下，所以最终 candidate 就是多数元素。时间 O(n)，空间 O(1)。