题源洛谷 P14357 [CSP-J 2025] 拼数 / number民间数据背景在算法竞赛和日常刷题中有一类问题看似是字符串处理本质上却是排序思想的灵活运用。这类问题里最常被低估、也最容易让人想复杂的就是贪心排序——明明一眼就能看出答案却总有人想写个通用排序、甚至动规。2025年CSP-J普及组的第一题《拼数》就是这类问题的典型代表。很多选手看到从字符串里挑数字拼最大整数第一反应是提取数字→存数组→sort降序→输出。这当然能AC但如果数据范围再大一点比如10 6 10^6106甚至10 7 10^7107通用排序的O ( n log ⁡ n ) O(n\log n)O(nlogn)就会成为瓶颈。而本题的数字只有0 ∼ 9 0 \sim 90∼9十种用计数排序可以把复杂度压到O ( n ) O(n)O(n)空间只需常数。本文将从这道真题出发系统梳理贪心排序的核心思想重点讲透计数排序在这类有限取值范围排序中的优雅应用并对比它与通用排序的取舍。一、为什么贪心排序能把问题变简单暴力算法的典型坏处是对每个可能的排列都枚举一遍找出最大值。全排列的复杂度是O ( n ! ) O(n!)O(n!)哪怕只有10个数字也直接爆炸。贪心排序的核心思想是利用比较规则的特殊性直接确定每个位置的最优选择从而避免枚举。举个例子。假设字符串里提取出的数字是[ 2 , 9 , 0 , 1 , 0 ] [2, 9, 0, 1, 0][2,9,0,1,0]要拼成最大的五位数。暴力做法会枚举5 ! 120 5! 1205!120种排列找出最大的92100 9210092100。但注意到多位整数的比较是从最高位开始的最高位放9 99一定比放2 22优第二位放2 22一定比放1 11优……以此类推。于是直接从大到小排序即可无需枚举任何排列。这就是贪心排序的魔法不是魔法是局部最优即全局最优。在拼最大数这个问题里每个位置独立地选择当前可用的最大数字最终结果就是全局最大。二、两种实现路径通用排序 vs 计数排序在动手写代码之前先建立一张决策表。几乎所有从有限集合中选取元素构造最优序列的问题都能归到下面两种实现。1. 通用排序基于比较的排序把数字提取出来存入数组或字符串调用std::sort并指定降序比较器。这是最直接、最不容易写错的做法。特征代码量少逻辑直观时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)由比较排序的下界决定适用于任意可比较的元素类型通用性强数据量n ≤ 10 6 n \leq 10^6n≤106时完全够用。2. 计数排序非比较排序由于数字只有0 ∼ 9 0 \sim 90∼9共10种取值用一个大小为10的数组统计每个数字出现次数然后从9 99到0 00依次输出即可。特征时间复杂度O ( n ) O(n)O(n)线性扫描即可完成空间复杂度O ( 1 ) O(1)O(1)固定大小为10的计数数组仅适用于取值范围很小且已知的场景是桶排序的最简形态也是基数排序的基石。三、计数排序从直觉到可复用模板3.1 计数排序到底在干什么把字符串想象成一条传送带我们用一个十格篮子cnt[0..9]来统计每种数字出现了几次。right不断把新字符扔进篮子如果是数字对应格子加一如果是字母直接跳过。统计完成后从篮子第9格倒着往回取取几个就输出几个——这就是最大的排列。计数排序特别适合两类问题元素取值范围极小例如数字0 ∼ 9 0 \sim 90∼9、字母a ∼ z a \sim za∼z、成绩0 ∼ 100 0 \sim 1000∼100等。需要稳定排序且数据量大例如10 7 10^7107级别的整数排序用计数排序或基数排序远快于快速排序。这两类题表面不同骨架几乎一样统计频次 → 按序输出 → 构造结果。3.2 万能模板伪代码如下初始化 cnt[0..9] 0 读取字符串 s for 每个字符 c in s: if c 是数字: cnt[c - 0] 1 for i 从 9 递减到 0: while cnt[i] 0: 输出 i cnt[i] - 1注意最内层的while可以换成for j in range(cnt[i])也可以直接用字符串乘法str(i) * cnt[i]拼接。核心思想不变按值从大到小按频次重复输出。下面用C写出更贴近实战的骨架#includebits/stdc.husingnamespacestd;intcnt[15];// 计数数组cnt[i] 记录数字 i 出现的次数string s;intmain(){cins;// 遍历字符串统计数字频次for(inti0;is.size();i){if(s[i]0s[i]9){cnt[s[i]-0];}}// 从 9 到 0 依次输出for(inti9;i0;i--){while(cnt[i]0){couti;cnt[i]--;}}coutendl;return0;}模板的价值不在于复制粘贴就能AC而在于把思考路径固定下来我先统计再按序输出注意力可以集中在如何过滤非数字字符和输出格式两处真正的差异上。刷题时最怕的是边写边想逻辑乱跳有了模板代码结构清晰调试也更快。3.3 例题《拼数》的计数排序实现题目给定字符串s ss仅含小写字母和数字且至少含一个1 ∼ 9 1 \sim 91∼9的数字。从中选取任意多个数字每个字符只能用一次按任意顺序拼成一个正整数求能拼成的最大值。思路窗口内维护数字出现次数。遍历字符串时数字字符对应格子加一非数字字符直接跳过。统计完成后从9 99到0 00依次输出每个数字的所有出现。#includebits/stdc.husingnamespacestd;intcnt[15];// 计数数组记录每个数字0-9出现的次数string s;intmain(){cins;// 统计每个数字出现的次数for(inti0;is.size();i){// 将字符转换为数字索引并增加对应计数if(s[i]0s[i]9){cnt[s[i]-0];}}// 从大到小输出数字9到0for(inti9;i0;i--){// 如果当前数字出现过if(cnt[i]!0){// 输出该数字的所有出现次数while(cnt[i]0){couti;// 输出当前数字cnt[i]--;// 减少计数}}}// 输出换行符coutendl;return0;}复杂度每个字符最多被访问一次统计时每个数字最多被输出一次输出时时间O ( ∣ s ∣ ) O(|s|)O(∣s∣)空间O ( 1 ) O(1)O(1)固定大小为10的数组。关键细节if (s[i] 0 s[i] 9)的判断必须加。虽然题目保证至少有一个数字但字符串中混有字母不加判断会导致cnt数组越界或产生垃圾数据。3.4 通用排序实现对比版如果你更习惯用std::sort代码可以这样写#includebits/stdc.husingnamespacestd;string s,ans;intmain(){cins;// 提取所有数字字符for(charc:s){if(c0c9){ansc;}}// 降序排序sort(ans.begin(),ans.end(),greaterchar());coutansendl;return0;}和计数排序的差异在哪里这里把排序交给了通用算法时间复杂度是O ( n log ⁡ n ) O(n\log n)O(nlogn)。对于10 6 10^6106的数据量两种方法都能通过但如果数据量达到10 7 10^7107或更高计数排序的线性优势就会显现。3.5 计数排序的「变体清单」把常见变体记成清单刷题时可以秒匹配场景做法数字0 ∼ 9 0 \sim 90∼9排序大小为10的计数数组小写字母a ∼ z a \sim za∼z排序大小为26的计数数组索引c - a大写字母A ∼ Z A \sim ZA∼Z排序大小为26的计数数组索引c - A成绩0 ∼ 100 0 \sim 1000∼100排序大小为101的计数数组需要稳定排序的整数基数排序多轮计数排序固定长度窗口其实是计数排序的退化取值范围就是窗口大小每个值出现0次或1次。3.6 什么时候不能用计数排序记住这句话计数排序依赖取值范围很小且已知。元素是任意整数如− 10 9 ∼ 10 9 -10^9 \sim 10^9−109∼109——范围太大数组开不下。元素是浮点数——无法直接作为数组下标。需要按自定义规则排序如按字符串长度——计数排序只能按值排序。需要排序的对象是结构体且按多个字段排序——要用稳定排序或自定义比较器。面试时若被追问为什么O ( n ) O(n)O(n)就答数字种类只有10种统计频次是线性扫描输出也是线性扫描整体两趟遍历。四、贪心排序的底层逻辑为什么降序就是最大4.1 字典序与高位优先多位整数的比较规则是字典序从最高位开始逐位比较第一位大的数整体更大与位数和后续位无关。例如910899因为第一位9 8 9 898后面不管怎么排都不影响结果。因此把最大的可用数字放在最高位是局部最优而每一位都局部最优就构成了全局最优。4.2 正整数的隐含约束题目要求输出正整数且保证至少有一个1 ∼ 9 1 \sim 91∼9的数字。这意味着不会出现全零的情况至少有一个非零数字且非零数字会排在零前面。不会出现前导零问题因为是从9 99到0 00输出零总是在最后。位数越多越好所有数字都用上位数最长且高位尽可能大。这些约束让贪心策略毫无后顾之忧不需要考虑要不要跳过某些数字全部用上就是最优。4.3 与拼接最大数问题的对比有一类经典问题给定若干数字字符串如[9, 34, 3]拼接成最大的数。这时候不能简单降序因为34和3的排序规则是343vs334需要自定义比较器ab ba。但本题每个数字都是单个字符不存在多位数字的拼接歧义所以纯降序即可。这是本题比经典题更简单的地方也是很多选手一眼看穿的原因。五、通用排序 vs 计数排序怎么选题可以用下面这张决策表快速分流元素取值范围很小如数字、字母、小范围整数且已知→ 优先想计数排序O ( n ) O(n)O(n)线性复杂度。元素取值范围大或未知或需要自定义比较规则→ 使用std::sort等通用排序O ( n log ⁡ n ) O(n\log n)O(nlogn)。数据量n ≤ 10 5 n \leq 10^5n≤105且代码正确性优先于性能→ 两种都可以选自己写得最顺手的。数据量n ≥ 10 7 n \geq 10^7n≥107且元素是整数或字符串→ 考虑基数排序字符串或计数排序整数避免O ( n log ⁡ n ) O(n\log n)O(nlogn)的常数开销。实际做题时先分类再写模板比一上来敲sort省很多时间。面试官也更喜欢你先说出为什么选这种排序再落代码。六、工程视角不止刷题计数排序和贪心思想不只是竞赛技巧工程里同样常见日志级别统计ERROR、WARN、INFO、DEBUG 只有四种用计数数组统计各类日志条数O ( n ) O(n)O(n)完成。字符频率分析文本处理中统计字母出现次数用于哈夫曼编码或简单加密分析。数据去重与压缩已知取值范围时用位图Bitmap或计数数组替代哈希表内存更省。基数排序的底层大数据排序框架中基数排序的多轮计数排序是核心模块。刷题时建立的按取值范围选择算法的习惯迁移到写业务代码时往往体现为更少的不必要开销和更干净的数据流。七、小结贪心排序的本质是利用比较规则的特殊性直接构造最优解避免枚举。计数排序 非比较排序 频统计计。先扫描统计再按序输出时间O ( n ) O(n)O(n)空间O ( k ) O(k)O(k)k kk为取值范围大小。通用排序 基于比较。代码简洁通用性强时间O ( n log ⁡ n ) O(n\log n)O(nlogn)适用于任意可比较元素。贪心策略 局部最优即全局最优。在拼最大数问题中高位放最大数字就是最优解的充要条件。回到《拼数》这道题它教会我们的不只是怎么写对更是怎么选对当数据范围极小且已知时不要惯性思维地写sort计数排序才是更优雅、更高效的答案。本文代码已在洛谷 P14357 上通过测试。如有错误或补充欢迎在评论区留言交流。