众数的选取
看完你能亲手求出众数，并说清多重众数与无众数的判定
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
众数的选取
看完你能亲手求出众数，并说清多重众数与无众数的判定
什么是「选取」问题
上一页我们认识了众数：数据中出现最多的那个值。但要在序列里「找到」某个特定排名的元素，比如第 3 小的数、中位数，这就叫选取问题。
「第 3 名是谁」对应「第 k 小的元素是谁」，不需要知道全部排序
中位数：秩居中的元素
上一页的众数是「数出来的」，这页换个思路：把全班身高从矮到高排队，站在正中间的那个人，就是中位数。找他，其实就是一个选取问题。
先按成绩排序排出名次，第三名对应秩为 3 的选手
众数的定义
上一页中位数靠「排第几」定位。众数换了个思路：不看位置，只数谁出现的次数最多——而且要压倒性地多，多到超过一半才算数。
举手人数超过全班一半，意见才能压倒所有其他选项
中位数必是众数（若有众数）
沿箭头从上往下读：先数众数的数量优势，再看它如何覆盖中位数的位置。
中位数未必是众数
中位数必是众数，前提是众数存在；一旦无众数，这条保证就失效了。
- 众数：出现次数严格最多
- 中位数秩居中，必落在众数上
- 取中位数即安全取到众数
- 所有元素出现次数并列
- 中位数只是普通元素
- 取中位数前需验证众数存在
频繁数：候选的推广
上一页我们看到：中位数和众数可能不是同一个人。那换个视角——不从位置，而从「出现得多频繁」来刻画候选元素，会发现它与序列的等长后缀存在漂亮的对应关系。
前半段攒下的领先优势，对应后半段被消耗的等长距离
减而治之的判定策略
从上往下看：序列按中位点切成前后两半，逐半扫描频繁数，任一命中即可确认众数。
候选数与计数的维护
一次扫描维护候选与计数：支持则加一，反对则减一，归零就换人。
众数选取算法实现
Boyer-Moore 投票法：一遍扫描维护候选数与计数，最后一步验证候选是否真是众数。
扫描中相异元素两两抵消，计数归零说明前缀内候选已无优势，可安全换人；若真众数存在，它必在抵消中存活至最后，但仍需第二遍验证。
自测：众数判定
对数组执行减而治之：若两元素相等则各留一个，否则同时删去两个。删空后剩下一个候选数 c，接下来该做什么？
要点收束
- ✓选取问题沿秩与频次两条主线展开
- ✓中位数和众数都由计数与比较刻画
- ✓中位数必是众数，反之不然
- ✓频繁数是众数的推广，候选数维护计数
- ✓减而治之：淘汰不占优候选再递归
课后思考
先合上笔记自己想一会儿，再对照参考答案——答案只是路径，不是终点。
参考答案回顾核心：众数定义为出现严格超过 n/2 次的元素。无众数时没有元素占绝对多数，中位数只是秩居中者，与「最频繁元素」无必然关联。
参考答案应用层：频繁数给出次数上界参考，若最频繁次数 ≤ n/2，可立即排除众数存在，省去完整验证；这提示把判定与统计结合。
参考答案迁移方向：超过 n/3 的元素至多两个，仿照成对抵消保留两个候选即可——这正是 Boyer-Moore 推广的思路，抵消规则需重新设计。