16 个数最多 20 次比较找出第二大
哪些公司问过
完美世界1
答案要点
- 锦标赛两两比较,15 次比较得出最大值
- 第二大只可能被最大值淘汰,候选为与冠军交手过的数
- 冠军共比赛 log2(16)=4 次,候选 4 个
- 候选中找最大需 3 次,总计 15+3=18 次
- 通用公式:n + ⌈log2 n⌉ - 2
易错点
- 以为第二大一定是决赛的失败者:它可能早在第一轮就被冠军淘汰
- 只记录比赛结果,不记录冠军击败过的对手
- n 不是 2 的幂时没处理轮空
面试官常见追问
- 为什么不能直接扫两遍?
- 代码上怎么记录与冠军交手过的数?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。