1. 先读懂这道题PTA里的“寻找大富翁”到底在考什么第一次在PTA题库里看到“7-1 寻找大富翁”这题时我的第一反应是“这不就是排序输出前M个嘛”。但刷完一遍以后我得说句实话这道题是典型的“看起来人畜无害实际暗藏杀机”的数据结构题目。如果你只用最朴素的冒泡排序去交大概率会在最后几个测试点拿到一个刺眼的超时。题目背景我重新梳理一下胡润研究院要发富豪榜输入N个人的财富值然后要求输出财富排名前M位的大富翁。N可能非常庞大M则相对小得多。输出要求按非递增顺序排列也就是从大到小排好再输出前M个。题目描述挺接地气但背后的本质其实是“从海量数据中高效提取Top K”的问题。这道题放在数据结构的题单里而不是单纯放在“排序算法”章节说明出题人想让你思考的并不是“会不会写排序”而是“面对超大规模输入时你能否根据数据特点选择合适的排序策略和数据结构”。这恰恰是工程开发里非常常见的场景日志Top K、搜索热词排行、销量榜、排行榜缓存更新全都是同一个模型。如果你正在复习数据结构、准备考研复试或者刷PTA准备机考我建议不要把这道题当成一道普通的排序题刷完就扔而是把它当作一次排序选型的训练。用不同思路各写一遍你会对整个排序体系的理解上一个台阶。适合谁看这篇内容正在刷PTA数据结构题集的学生、准备考研机试的考生、以及想补一补海量数据Top K思路的开发者。我会把题目拆开讲清楚把几种解法的思路、复杂度、适用场景、踩坑点都摆出来最后附上可以直接提交的代码版本。1.1 输入输出格式与数据范围先说清楚原题大致是这样的输入第一行给出两个正整数 N 和 M其中 N 是总人数M 是要输出的富翁数量N 可能非常大M 小于等于 N。第二行给出 N 个正整数代表每个人的财富值。输出要求按非递增顺序输出财富值最大的 M 个数数字之间用空格分隔行尾不能有多余空格。关键信息就是 N 的规模。PTA 的原题数据范围我记得 N 最大能到百万级别M 最多不会超过 100具体以平台版本为准但“N巨大、M小”是这类题目的通用设定。这个数据特点几乎直接决定了“全排序”不是最优解。很多人拿到题第一反应是“先读进来sort一下输出前M个”这在数据量小的时候完全没问题。但 N 到百万级之后一次全排序的时间开销是很可观的。而且题目明显是冲着“Top K 问题”去设计的你如果只会全排列那这道题只能算“勉强过”谈不上“真正掌握”。1.2 为什么要单独研究Top K而不是直接排序聊天的时候经常有同学问我“Top K 不就是排序后取前K个吗有必要专门讲吗”有必要而且非常有必要。Top K 问题的核心是“不关心完整有序的整体只关心极端头部的那一小撮”。打个比方学校要表彰全校成绩最高的10个人你不需要把全校两万人的成绩全部按高低排成一个长名单你只需要不断扫一遍保留当前见过的最高的10个就够了。这个“保留当前最优的K个”的思想正是堆和快速选择这类方案存在的原因。从复杂度上看全排序的时间至少是 O(N log N)而维护一个大小为M的堆只需要 O(N log M)。M远小于N的情况下这差距非常明显。如果 M 是常数级别比如 M100那堆解法几乎可以当作 O(N) 来用。再加上输入规模本来就大IO 和内存访问的开销也要算进去排序选型直接决定你的代码是“勉强通过”还是“稳稳定过”。2. 解法一先全排序再输出为什么有时候也能过在给出最优解之前先聊聊最朴素的思路。毕竟研究一个方案“为什么不够好”能帮助你更深刻地理解最终方案为什么好。2.1 基于冒泡排序的“部分冒泡”思路我第一次做这道题时脑子里闪过的第一个念头其实是“冒泡排序的改进版”。因为冒泡排序每一趟能把当前未排序部分的最大值“冒”到末尾那我只需要执行 M 趟就能确定前 M 个最大值。这套思路的代码如下#include stdio.h int main() { int n, m; int a[1000005]; scanf(%d %d, n, m); for (int i 0; i n; i) { scanf(%d, a[i]); } if (m n) m n; for (int i 0; i m; i) { for (int j 0; j n - i - 1; j) { if (a[j] a[j 1]) { int temp a[j]; a[j] a[j 1]; a[j 1] temp; } } } for (int i n - 1; i n - m; i--) { if (i ! n - 1) printf( ); printf(%d, a[i]); } return 0; }这个思路看起来“只排了M趟”比完整冒泡要快但仔细算一下每趟内部要比较 n-i-1 次M趟下来时间复杂度是 O(N*M)。如果 N 是一百万、M 是100那就是一亿次比较在PTA的时限下基本处于“可能超时”的危险边缘。这个方案的价值在于让你直观感受到“部分排序”的出发点我们确实不需要把整个数组排好只需要把最值“捞”出来。但用冒泡去捞效率太低了每趟都要扫描全数组做了大量重复工作。2.2 直接调用库函数排序的利弊如果题目允许最省事的办法是直接用 C 的 qsort 或者 C 的 sort。完整排序一次时间复杂度 O(N log N)然后输出前M个。#include bits/stdc.h using namespace std; int main() { int n, m; scanf(%d %d, n, m); vectorint a(n); for (int i 0; i n; i) scanf(%d, a[i]); sort(a.begin(), a.end(), greaterint()); for (int i 0; i m; i) { if (i) printf( ); printf(%d, a[i]); } return 0; }这段代码非常短而且在小数据量下绝对没问题。但问题还是出在数据规模上N 到百万级以后sort 虽然快但仍然是对整个数据集排序做了很多“无用功”。很多PTA版本的数据强度会让全排序版本在最后一个测试点超时。更关键的是如果面试官问你“有100亿条数据内存装不下你怎么办”全排序的思路直接失效——因为你根本不可能把所有数据读进内存再排序。所以全排序的思路只能算“保底方案”用来帮助你理解问题不是这道题想让你交的答案。3. 解法二最小堆维护Top M这是最推荐的“标准答案”堆这个数据结构几乎是海量数据 Top K 问题的默认解法。选最小堆而不是最大堆是很多人第一次接触时会困惑的地方我单独拿出来讲。3.1 为什么找前M大要用“最小堆”而不是“最大堆”直觉上要“找最大值”我们第一反应是维护一个最大堆堆顶是最大的数。但仔细想一下场景你要在源源不断的数据中保留最大的M个你真正需要快速判断的是“新来的数够不够格进入前M”以及“如果够格应该把当前前M里最小的那个踢出去”。也就是说你维护的这个集合需要能随时访问到“当前最小值”。这正好是最小堆的强项堆顶就是最小值。用一个生活中的例子来说你是一个选秀节目的评委场上只能留 M 个选手。每面试一个新选手你只需要看一眼台上最弱的那位是谁如果新选手比TA强就把最弱的换掉。你根本不需要知道台上谁是第一名你只需要知道谁是“守门员”。最小堆的堆顶就是那个“守门员”。具体操作如下建立一个大小为 M 的最小堆。读入前 M 个数据建立初始堆。继续读入后续数据每读一个数 x如果 x 大于堆顶元素说明 x 比当前前M个里最小的那个还大那就用 x 替换堆顶然后向下调整堆。如果 x 小于等于堆顶元素说明 x 连“守门员”都打不过直接丢弃。全部数据处理完后堆里的 M 个元素就是前 M 大的数。因为要按非递增顺序输出最后把堆内元素依次取出排序再输出。这个方案的时间复杂度非常漂亮。建堆 O(M)后面 N-M 个数每个最多触发一次调整 O(log M)整体 O(N log M)。空间复杂度 O(M)在海量数据场景下几乎是最优的。3.2 图解最小堆调整流程文字描述干巴巴我描述一下动态过程你可以在纸上画一遍假设 M5堆里已经有5个数12, 5, 18, 9, 7构建成最小堆后堆顶是5。新来一个数 10比堆顶的5大于是把堆顶替换成10此时堆变为 10, 12, 18, 9, 7这个数组不满足堆性质了。从堆顶开始向下调整比较10和它的两个孩子12、18选择较小的12但10比12小不用换再往下10的孩子是9和7选择较小的7但10比7大所以把10和7交换。调整完之后堆为 7, 12, 10, 9, 18。堆顶是7也就是当前堆里的最小值。下次再来新数继续跟7比较。这个“替换堆顶再调整”的过程就是堆排序里“重新堆化”的简化版。你只需要保证堆顶是当前最小的不需要关心其他位置的细节。3.3 C语言版手写最小堆完整代码如果你在PTA上用的是纯C那需要自己把堆写一遍。这也是数据结构题目该有的样子“会用库”不算本事“能实现”才叫真会。完整代码我贴在下面重点看堆的调整逻辑。#include stdio.h int heap[105]; // 堆数组M最大100左右这里开大一点 int m; // 向下调整以 i 为根节点的子树调整为最小堆 void siftDown(int i, int length) { int temp heap[i]; int child 2 * i; while (child length) { if (child 1 length heap[child 1] heap[child]) { child; } if (temp heap[child]) { heap[i] heap[child]; i child; child 2 * i; } else { break; } } heap[i] temp; } int main() { int n, x; scanf(%d %d, n, m); if (m n) m n; // 先读入前 m 个元素 for (int i 1; i m; i) { scanf(%d, heap[i]); } // 建堆从最后一个非叶子节点开始调整 for (int i m / 2; i 1; i--) { siftDown(i, m); } // 处理剩余元素 for (int i m 1; i n; i) { scanf(%d, x); if (x heap[1]) { heap[1] x; siftDown(1, m); } } // 堆排序把堆里的元素从小到大取出来然后逆序输出 int len m; while (len 1) { int temp heap[1]; heap[1] heap[len]; heap[len] temp; len--; siftDown(1, len); } for (int i m; i 1; i--) { if (i ! m) printf( ); printf(%d, heap[i]); } return 0; }这段代码有几个细节要注意堆数组下标从1开始这样孩子节点下标就是 2i 和 2i1写起来方便也不容易搞混。建堆时从 m/2 开始向前循环因为叶子节点没有孩子不需要调整。最后输出前我用的是“堆排序”的方式把堆内元素从小到大放到数组尾部然后逆序输出这样就能得到非递增序列。注意这一步对 M 个元素排序复杂度只有 O(M log M)M很小无所谓。3.4 C版优先队列极简写法如果你用的是C那代码量还能再压缩不少。优先队列 priority_queue 就是现成的堆。要注意的是priority_queue 默认是最大堆所以这里要用 greater 来声明一个最小堆。#include bits/stdc.h using namespace std; int main() { int n, m, x; scanf(%d %d, n, m); if (m n) m n; priority_queueint, vectorint, greaterint pq; for (int i 0; i n; i) { scanf(%d, x); if (pq.size() m) { pq.push(x); } else if (x pq.top()) { pq.pop(); pq.push(x); } } vectorint ans; while (!pq.empty()) { ans.push_back(pq.top()); pq.pop(); } reverse(ans.begin(), ans.end()); for (int i 0; i ans.size(); i) { if (i) printf( ); printf(%d, ans[i]); } return 0; }这里优先队列的大小一直维持在 M堆顶就是当前前M个里最小的。每来一个新数如果比堆顶大就淘汰堆顶换新人。整个过程非常干净几乎就是 Top K 问题的标准模板。提示不要一上来就写 priority_queue 版本交差。我建议你先把C语言版本自己敲一遍体会“堆顶变化需要从根向下调整”这个过程然后再用C的库函数写一遍。两种能力不等价面试手写堆的时候没人让你调库。4. 解法三基于快速排序思想的快速选择追求平均O(N)如果你觉得堆的思路已经够好了那我要告诉你还有另一种思路在“只需要输出前M大而不需要维护一个动态集合”的静态数据场景下平均复杂度能做到 O(N)。它就是快速选择基于快速排序的 partition 思想。4.1 快速选择的原理每次都扔掉一半快排的思路是选一个基准数把数组分成左小右大两部分然后递归排序两边。快速选择则更“偷懒”——它只关心第 M 大的数应该在哪个位置并不关心左右两边内部是否有序。具体做法用 partition 把数组分成两部分左边都大于等于基准值右边都小于基准值这里按本题目的大到小来排。假设 partition 返回的基准位置是 pospos 左边包括pos的元素都大于等于基准。如果 pos 恰好等于 M-1说明从 0 到 pos 正好是前 M 大的数直接输出。如果 pos 大于 M-1说明前 M 大都在左半部分递归处理左半部分。如果 pos 小于 M-1说明左边还不够需要去右半部分再找一部分。每次递归只需要处理数据规模的一半所以理想情况下时间复杂度是 O(N N/2 N/4 ...) O(N)。最坏情况每次基准都选到极值会退化到 O(N^2)所以通常配合随机化选基准来规避。这个思路和快排很像但在 Top K 场景下快排要对两半都递归快速选择只对一边递归省掉了大量无用排序。4.2 快速选择完整代码实现我这里用一个比较直观的写法以数组下标 0 为左边界n-1 为右边界partition 后返回基准最终位置。#include bits/stdc.h using namespace std; int a[1000005]; int n, m; int partition(int left, int right) { // 随机选基准避免最坏情况 int idx left rand() % (right - left 1); swap(a[left], a[idx]); int pivot a[left]; int i left, j right; while (i j) { while (i j a[j] pivot) j--; a[i] a[j]; while (i j a[i] pivot) i; a[j] a[i]; } a[i] pivot; return i; } void quickSelect(int left, int right, int k) { if (left right) return; int pos partition(left, right); if (pos k - 1) return; else if (pos k - 1) quickSelect(left, pos - 1, k); else quickSelect(pos 1, right, k); } int main() { srand(time(0)); scanf(%d %d, n, m); if (m n) m n; for (int i 0; i n; i) scanf(%d, a[i]); quickSelect(0, n - 1, m); sort(a, a m, greaterint()); for (int i 0; i m; i) { if (i) printf( ); printf(%d, a[i]); } return 0; }这段代码的核心只有 quickSelect 函数。partition 完成之后左边的所有数都大于等于基准右边都小于等于基准。如果基准位置正好是 k-1说明 0 到 k-1 这一段就是我们要的前M个元素。最后再对这些元素做一次排序保证输出顺序正确。因为 M 很小最后一步无所谓。这个方案在平均情况下的速度比堆更快一点因为少了 log M 的常数。但它的缺点是需要对整个数组进行原地修改如果后面还想用到原始数据就不行了。另外它没有“在线处理”能力如果数据是流式输入的必须等全部读入才能开始。这两种方案各有适用场景属于互补关系。4.3 什么时候用快速选择什么时候用堆不少教材会把这两个方案并列但没说清楚选型依据。我根据自己的经验整理了一下场景推荐方案原因数据一次性给全且只查一次快速选择平均 O(N)速度最快数据流式到达、逐条输入最小堆不需要等待全部数据边读边处理需要多次查询不同的 K堆或全排序堆可以保存前K个集合全排序一劳永逸内存非常紧张最小堆只需要 O(K) 空间不用存全部数据需要保证最坏情况稳定最小堆堆操作的时间复杂度是严格 O(log K)不会退化实际工程里海量日志分析、实时排行榜这种东西一般都用堆。因为数据并不是一次性给全的而是源源不断产生。而算法题里如果数据给全了快速选择往往表现更好。这道题是PTA的静态输入所以堆和快速选择都能稳过你可以都写一遍。5. 延伸思考这题背后的工程场景与变式题目“寻找大富翁”不只是PTA题库里的一道题它背后对应的工程场景几乎无处不在。如果你面试时能把这道题引申到实际业务里会非常加分。5.1 Top K 问题的真实应用排行榜、日志分析、用户画像举几个最典型的场景你可能每天都在接触短视频平台的“热榜”功能。每天的播放量数据是海量的但要展示的只有前50条。后台不可能每次都把全量数据重新排序而是维护一个大小为50的最小堆新数据到了就往里走一遍实时更新榜单。堆顶就是“第50名”是入场门槛。日志系统的“高频错误排查”。假设系统一天产生上亿条日志你需要找出出现次数最多的10种报错。做法是先哈希统计每种错误的数量然后用最小堆找 Top 10。整个过程和“寻找大富翁”一模一样只不过“财富值”变成了“出现次数”。搜索引擎的“热门搜索词”。搜索日志源源不断进来系统需要实时显示热搜榜。那就是一个动态 Top K 问题堆依然是首选方案。这些场景和PTA题目的本质完全一致“在无法全量排序或全量排序太浪费的情况下用最少的代价保留头部数据”。5.2 如果数据带“权重统计”该怎么做变式原题给的是已经算好的财富值直接比较大小就行。但很多时候原始输入是“每个ID出现了多少次”你需要统计之后才能得到“财富值”。这种问题就变成了“先词频统计再Top K”。典型的做法是哈希表加最小堆两步走先用哈希表或字典统计每个元素出现的次数。遍历哈希表维护一个大小为K的最小堆堆的排序规则是按出现次数比较。输出堆里的元素。这相当于给“寻找大富翁”套了一层“预计算”的外壳核心的 Top K 逻辑完全不变。很多面试题会考这种组合题型比如 LeetCode 上的“前 K 个高频元素”本质就是这个。5.3 海量数据内存放不下时的优化思路如果数据量真的巨大大到连一次完整的遍历都无法接受比如上千亿条数据分布在多台机器上那单机的最小堆就不够了。这时一般会引入分治思想把数据分片每台机器分别用堆找出自己的前M个最后再合并各路结果做一次“多路归并”。这就是 MapReduce 框架里 Top K 任务的经典做法。回到PTA这道题虽然数据规模只是在百万级别不至于上分布式但明白这个“分片-局部TopK-归并”的思路能帮你在未来碰到真正海量数据时知道路线图是什么样。这也是为什么很多人说“数据结构学的是思想不是死记硬背”的原因。6. 常见问题与踩坑实录从提交失败到顺利AC最后这部分我把刷这道题时容易踩的坑集中列出来。这些坑有些是我自己踩过的有些是帮学弟学妹调试时遇到的每一个都真实发生过。6.1 堆数组越界问题手写堆时数组下标从1开始开数组很容易忘记多开一位。如果你声明int heap[100]而 M 恰好是100那访问 heap[100] 就越界了。正确做法是至少开int heap[105]或者直接按题目的上限加个10。这种错误在本地不一定能发现但PTA的判题环境可能会报运行时错误很难排查。注意手写堆时数组长度一定要比需要的容量多开几个不要卡着边界开。同理存放全部数据的数组 a[1000005] 如果 N 最大是1000000也要多开5个左右防止循环边界写错时越界访问。6.2 没有判断 M 是否大于 N有的测试点是 M 大于 N 的情况。原题虽然说了 M≤N但严谨一点程序里加上if (m n) m n;是零成本的保险。我见过有同学堆数组开得正正好好然后 M 比 N 大读入时直接越界整个程序崩掉。加这一行也就是一行代码的事不要省。6.3 输出格式错误末尾空格、换行缺失PTA对输出格式的要求非常严格。数字之间要用一个空格分隔但行末不能有多余空格。很多同学会在输出循环里无脑printf(%d , a[i])结果末尾多了一个空格被判“格式错误”。我的习惯是for (int i 0; i m; i) { if (i) printf( ); printf(%d, ans[i]); } printf(\n);这样第一项前不加空格之后每项前加一个空格末尾就不会有空格了。最后记得补一个换行虽然PTA有时不检查换行但养成好习惯总没错。6.4 堆里元素不足 M 个的情况如果原始数据本身不足 M 个虽然题目保证了 N≥M但边界情况下 M 可能被改成 N堆在输出阶段可能会出现下溢。加上if (m n) m n;就是为了把这个问题扼杀在摇篮里。另外优先队列版本里用pq.size() m来控制入堆数量也能避免这个问题。6.5 用 cin/cout 导致超时C 的 cin/cout 默认和 C 的 stdio 同步效率比 scanf/printf 慢很多。在百万级输入的题目里cin/cout 甚至可能导致超时。两个解决办法直接用 scanf/printf。在 main 开头加一句ios::sync_with_stdio(false); cin.tie(0);。我个人写PTA的习惯是数据量大的题目一律用 scanf/printf省心。6.6 快速选择里的随机化问题快速选择如果固定选第一个元素做基准在面对有序数据时可能退化成 O(N^2)直接超时。这就需要在 partition 里加随机化int idx left rand() % (right - left 1); swap(a[left], a[idx]);随机选基准能大概率避免最坏情况。C语言版本记得在 main 里调用srand(time(0))设置随机种子。不设置随机种子的话rand() 每次运行都返回相同的序列等于没有随机。7. 我的个人体会为什么这道题值得反复做几遍“寻找大富翁”这道题看起来是PTA题单里不起眼的一道但我后来在面试里被问到过很多次相关的问题。有一次面试官问“如何实现一个排行榜数据是实时产生的”我直接把这题的思路讲了一遍面试官明显眼神亮了。还有一次面试问“给你一千亿条URL找出访问量最大的100个”也是同样的模型哈希统计加最小堆。这题刷透了后面能省很多事。我个人建议你把这道题至少写三遍第一遍直接用内置排序感受一下题目的数据强度也理解为什么全排序在数据量大时会吃力。第二遍手写最小堆认真走一遍建堆、调整、淘汰的过程。写完以后顺手把堆排序也复习一遍数据结构课的知识点一下就串起来了。第三遍试试快速选择感受一下“只排一半”和“全排”在效率上的差异。如果还有余力可以想想如果数据是文件流形式代码应该怎么改。每种解法对应的是不同的工程考虑排序是通用方案但浪费堆是动态场景的利器空间友好快速选择是静态数据的性能王者。把三者的适用边界弄清楚比单纯“AC掉一道题”有价值得多。最后再分享一个小技巧PTA 这题的代码框架是可以用在很多同类题上的。只要把输入的“财富值”换成“出现次数”“评分”“点击量”逻辑几乎不用改。刷题库时多留个心眼把题目归类成模板你的复习效率会高很多。
