数字次数排序这道题我第一眼扫过去的时候心里想的是送分题统计频次再排个序两行代码的事。结果真坐下来写从读入方式到并列项的次序再到输出格式前前后后被卡了不止一次。这道题出自蓝桥杯省赛Python组属于那种规则一句话、考点一大片的典型题目数字次数排序看着只是排序实际把哈希计数、多关键字排序、稳定性、输出格式这几件事一次性考全了。它适合两类人看一类是刚接触算法题、想把计数加排序这套组合拳打扎实的初学者另一类是刷过不少题但总在这种看着简单的题上丢分的老手。下面我按自己真实的解题顺序把这道题从规则拆解到代码落地再到各种变体和坑完整走一遍。1. 题面那一句话里藏着的三个考点1.1 把次数优先、数值兜底翻译成排序键原始题目的规则可以概括成一句话给一个长度为 n 的整数序列按每个数字出现的次数从多到少排序出现次数相同的数字按数值本身从小到大排序。这句话的信息密度其实很高。它明确给出了两级排序优先级第一级是出现次数方向是降序第二级是数字本身的值方向是升序。两级方向不一致这是很多人第一遍写错的地方——顺手写成keylambda x: (x[1], x[0])次数变成升序了样例一跑就露馅。再往下拆这句话还隐含了两件事。第一输出的到底是原序列重排还是每个不同的数字输出一次题目描述里通常写得比较含蓄我当时的做法是先看样例输出的长度如果输出长度等于 n那就是保留重复元素的重排如果输出长度等于不同数字的个数那就是去重后再排。第二出现次数这个信息本身要不要一起输出有些版本要求输出数字 次数的成对形式有些只输出数字。这两点如果判断错逻辑再对也是零分。所以拿到这类题我的固定动作是先花三十秒把输入是什么、输出是什么、输出多长三件事在纸上写清楚再动键盘。这不是啰嗦是我在省赛这种限时场景下用丢分换来的习惯。1.2 为什么出题人喜欢把这道题放在前面从命题角度想这道题放在省赛的前几题位置非常合理。它同时考察三种能力用字典做频次统计、用自定义 key 做多关键字排序、按格式输出结果。这三件事都是 Python 刷题的地基任何一项不牢都会在这里暴露。而且它有个好处——解法分层特别明显。会暴力的人能拿一部分分会字典的人能拿满分会Counter的人能写得更短但短不等于对Counter.most_common()在并列次数上的行为就让不少人栽过。题目简单但每一层都有细微差别这正是它的价值所在。1.3 数据规模决定了你能不能用暴力题目一般会给 n 的范围比如 n 不超过 10 万数值范围在某个区间内。这个信息必须看因为它直接决定算法选择。如果 n 是 1000 以内双重循环暴力统计完全没问题代码十行搞定。如果 n 到 10 万双重循环就是 100 亿次操作Python 里跑一天也出不来。我见过有人不看数据范围直接写暴力本地小样例跑得飞快一交上去大面积超时还以为是评测机的问题。这里有个经验看到 n 的数量级先在心里估一遍操作次数。Python 每秒大概能跑千万级别的简单操作10 万数据的 O(n log n) 排序毫无压力10 万数据的 O(n²) 就是灾难。这个心算习惯养成之后选解法的速度快很多。2. 三种写法从能跑到跑得快2.1 暴力统计思路最直白代价最昂贵最朴素的想法是对序列里每一个元素都完整扫一遍整个序列数它出现了几次然后带着这个次数去排序。def count_brute(nums): n len(nums) result [] for x in nums: cnt 0 for y in nums: if y x: cnt 1 result.append((x, cnt)) result.sort(keylambda p: (-p[1], p[0])) return result这段代码逻辑上没错样例也能过。问题在于它做了大量重复劳动——数字 7 出现了 50 次它就把数 7 的个数这件事重复做了 50 遍。整体复杂度是 O(n²)而且排序的 key 里带着重复的统计结果等于白算。我提这段不是为了让你用而是想说清楚为什么需要哈希表。哈希表的价值就在于把重复查询同一件事变成只算一次之后 O(1) 取用。理解了这一点后面所有写法都是自然推导出来的。2.2 字典计数加 sorted最稳的标准骨架标准解法分两步先用字典把每个数字的出现次数统计出来再对字典的键值对排序。import sys def solve(): data sys.stdin.read().split() if not data: return n int(data[0]) nums list(map(int, data[1:1 n])) freq {} for x in nums: freq[x] freq.get(x, 0) 1 items sorted(freq.items(), keylambda kv: (-kv[1], kv[0])) out [] for value, cnt in items: out.extend([str(value)] * cnt) print( .join(out))逐段说下为什么这么写。sys.stdin.read().split()一次性把全部输入读进来按空白切分这个写法对数据可能跨多行的情况天然免疫。有些题目样例里数字排成一行实际测试数据可能换行、可能有多余空格用input()逐行读再拼接容易出错用read().split()一劳永逸。freq.get(x, 0) 1是字典计数的经典写法比if x in freq判断少一次哈希查找代码也更紧凑。数据量大的时候这个细节能省一点时间。排序的 key 是(-kv[1], kv[0])。这里用了个小技巧次数取负把降序问题转成升序问题。因为 Python 的排序默认是升序而元组比较是从左到右逐项比所以-cnt小的排在前面等价于 cnt 大的排在前面cnt 相同时再比 valuevalue 小的在前。这一行是整个解法的核心。最后输出部分out.extend([str(value)] * cnt)是把每个数字按它的出现次数展开。这一步对应输出原序列重排的版本。如果题目要求去重输出就把这个循环换成out.append(str(value))即可。2.3 Counter 的甜头与它埋的雷collections.Counter是 Python 处理频次统计的利器一行就能完成计数from collections import Counter freq Counter(nums) items freq.most_common()很多人的第一反应是most_common()出来就是答案直接输出。这里必须踩一脚刹车。most_common()的语义是按计数从大到小返回对于计数相同的元素它不保证按数值大小排序。源码层面当不传参数时它内部走的是sorted(self.items(), key_itemgetter(1), reverseTrue)而 Python 的 sorted 是稳定排序稳定意味着相等的元素保持原有顺序——原有顺序是什么是元素第一次被插入 Counter 的顺序也就是在原序列中首次出现的位置。所以如果你的输入是5 5 3 3 9most_common()给出的并列项顺序取决于 5 和 3 谁先出现跟数值大小没关系。这种错误特别隐蔽因为样例有时候恰好顺序对上了你根本发现不了。稳妥的写法是把most_common()的结果再接一次排序items sorted(freq.items(), keylambda kv: (-kv[1], kv[0]))绕了一圈回到同一个 key 函数上。所以我的建议是这道题直接用 sorted 加自定义 key别贪 Counter 那一行的方便。除非你确定规则里没有并列时的次序要求。提示如果确实想用 Counter 又要处理并列可以写sorted(freq.items(), keylambda kv: (-kv[1], kv[0]))等价于先 most_common 再按值稳定排一次但没必要绕。3. 排序键的三种造法各有各的适用面3.1 元组加负号最省事也最常用前面用的(-cnt, value)是这道题的最优写法简短、无依赖、速度快。它的适用前提是所有参与排序的字段都能取负也就是必须是数值类型。这个前提在本题里成立因为次数一定是正整数数值也是整数。但如果题目改成按字符串字典序-x[0]就直接报错了。所以这个技巧不是万能的用之前先确认类型。顺带说一个细节(-cnt, value)里的负号是作用于整个字段不是作用于排序结果。有人会写成keylambda kv: (kv[1], kv[0])然后加reverseTrue那就变成次数降序、数值也降序了第二级关键字方向反了。这种错误在检查的时候很难一眼看出来因为次数部分是对的。3.2 cmp_to_key能表达任意规则但慢Python 3 的 sorted 只接受 key 函数不接受比较函数。如果规则复杂到没法用一个 key 元组表达就得请出functools.cmp_to_keyfrom functools import cmp_to_key def cmp(a, b): if a[1] ! b[1]: return -1 if a[1] b[1] else 1 return -1 if a[0] b[0] else (0 if a[0] b[0] else 1) items sorted(freq.items(), keycmp_to_key(cmp))这段代码跑起来是对的但它的常数因子比 key 版本大好几倍因为每次比较都要调用一次 Python 函数而 key 版本只在对每个元素求 key 时调用一次。数据量上万的时候差距就明显了。我的原则是能用 key 表达就绝不写 cmp。这道题的规则用元组完全能表达cmp_to_key 属于知道有这么个东西就够了。3.3 先分桶再拼接绕开排序的思路还有一种思路值得提一句虽然不是主流。既然次数的取值范围只可能是 1 到 n那就可以按次数分桶from collections import defaultdict buckets defaultdict(list) for value, cnt in freq.items(): buckets[cnt].append(value) out [] for cnt in sorted(buckets.keys(), reverseTrue): for value in sorted(buckets[cnt]): out.extend([str(value)] * cnt)这个写法把两级排序拆成外层按次数降序、内层按数值升序逻辑非常清晰特别适合次数范围小、数值分布集中的场景。缺点是代码长、常数开销大本题用不上。但如果是按出现次数分组输出这种变体题分桶的思路反而更自然。我把这个写出来是想说同一道题不该只有一种写法。当你把规则理解透了代码只是表达方式的选择反过来如果只会背一种模板规则一改就傻眼。4. 我在调试这道题时踩的六个坑4.1 输入没读完就开始算最开始的版本我是这么写的n int(input()) nums list(map(int, input().split()))本地样例一跑对了。交上去错了。原因很简单测试数据的 n 个数字未必挤在一行里可能是三行、五行甚至中间夹空行。input()只读一行后面的数据全丢。正确做法是全部读进来再切data sys.stdin.read().split() n int(data[0]) nums list(map(int, data[1:1 n]))注意data[1:1 n]这个切片它保证即使输入里有多余的内容也只取前 n 个防止脏数据混进统计。4.2 该去重的时候没去重这一步的错误方向有两个都很常见。方向一题目要求每个数字只输出一次你却按次数展开成了原序列长度。方向二题目要求输出完整重排序列你却只输出了不同的数字。判断依据只有一个——看样例输出。如果样例输入的 n 是 8输出也是 8 个数那就是保留重复如果输出只有 4 个数那就是去重。我的笨办法是写代码之前在注释里写一行# 输出长度 n 还是 不同数字个数跑完样例先核长度长度对了再看内容。这个动作花不了三秒但能挡掉一大类错误。4.3 次数降序写成了升序keylambda kv: (kv[1], kv[0])和keylambda kv: (-kv[1], kv[0])只差一个负号肉眼几乎看不出来但输出结果完全不同。排查方法很直接造一个次数差异明显的测试数据比如[1,1,1,2,2,3]正确的输出应该以三个 1 开头。如果开头是 3说明方向反了。养成自己造一组能区分方向的数据的习惯比盯着代码看十分钟管用。4.4 负数和零的处理如果题目里的数字可以取负(-cnt, value)这个写法依然成立因为负号作用在次数上跟数值本身的正负无关。但要注意另一件事数值排序的方向。规则说的是数值从小到大那 -5 就应该排在 3 前面Python 的默认整数比较正好是这个语义不需要特殊处理。真正容易出问题的是用字符串做键的场景。10 9在字符串比较下是 True因为逐字符比的时候 1 9。如果你的数字被当作字符串处理排序结果会完全错乱。所以只要题目没说按字典序就老老实实转 int。4.5 Counter.most_common 的并列顺序前面提过这里再强调一次因为它真的太容易中招。most_common()在计数相同时按插入顺序返回插入顺序又取决于元素在输入里的首次位置。输入顺序一变输出就变而样例往往看不出这个问题。我当时的排查过程是这样的先本地跑通样例再自己造了一组并列数据发现输出顺序和预期不符然后去查most_common的行为才意识到问题。这个链路值得记住——样例过了不代表对一定要造边界数据。4.6 输出格式的细节print( .join(out))是最常见的输出方式。但有两处坑。第一处如果out是空的比如 n 为 0 或者数据异常 .join([])返回空字符串print出来是一个空行某些评测机对空行是敏感的。稳妥的做法是加个判断。第二处如果题目要求每个数字一行那就得用\n.join(out)。这个不能靠猜必须看题面的输出说明。我整理了一张排查表遇到错误时可以对着过一遍现象最可能的原因定位方法部分测试点通过部分超时用了 O(n²) 暴力统计看 n 的范围改字典计数全部答案错误但格式正常次数排序方向反了造[1,1,1,2,2,3]验证并列项顺序不对用了 most_common 未二次排序造次数相同的两组数据输出长度不对去重与展开搞混了对比样例输出长度运行时报错 IndexError输入切片越界或数据不足打印 data 长度核对数字顺序错乱像字符排序键里混入了字符串检查是否漏了 int 转换5. 规则一改代码该往哪儿动5.1 次数相同按数值从大到小这是最常见的变体。改动只在排序键上把kv[0]换成-kv[0]。items sorted(freq.items(), keylambda kv: (-kv[1], -kv[0]))两个字段都取负整个排序就变成次数降序、数值降序。如果数值可能很大又不想取负也可以写成两级显式判断但元组加负号更简洁。这类改动看起来微不足道但它揭示了一个重要认知多关键字排序的本质是把多个比较维度编码进一个可比较的对象里。只要你能构造出这个对象规则怎么变都能应对。5.2 次数相同按首次出现位置这个变体在真实业务里比按数值排序更常见。比如统计热搜词同样热度的词应该按上榜时间先后展示而不是按词本身的编码排。实现方法是记录每个数字第一次出现的位置first_pos {} for i, x in enumerate(nums): if x not in first_pos: first_pos[x] i items sorted(freq.items(), keylambda kv: (-kv[1], first_pos[kv[0]]))这里 key 函数里引用了外部的first_pos字典闭包捕获完全合法。注意if x not in first_pos只在首次出现时写入后面的重复出现不会覆盖这正是我们要的语义。5.3 按字符串字典序排有些题目的输入直接就是字符串比如统计字符出现次数。这时候数字转字符串的坑就来了10排在9前面。如果题目确实要求字典序那就照做但要在心里明确这是字典序不是数值序。如果题目说的是按大小那就必须先转成数字再排。判断依据还是题面用词字典序、ASCII 顺序是一个意思数值大小、从小到大是另一个意思。items sorted(freq.items(), keylambda kv: (-kv[1], kv[0])) # 如果 kv[0] 是字符串这里就是字典序5.4 只输出出现次数前 k 的数字这是把题目往 Top-K 方向延伸。改动点有两处排序之后做切片以及处理第 k 名出现并列的情况。items sorted(freq.items(), keylambda kv: (-kv[1], kv[0])) k 3 result items[:k]如果要求并列第 k 名全部输出就不能简单切片得先取第 k 名的次数阈值再把所有达到阈值的挑出来if len(items) k: threshold items[k - 1][1] result [it for it in items if it[1] threshold]这两种语义在实际场景里差别很大题目怎么说就怎么实现别自作主张。6. 从这道题里能带走的通用套路6.1 计数加排序的模板可以固化下来把这道题的骨架抽出来其实是一个很通用的模式遍历一次建频次表再对频次表的多关键字排序最后按规则展开输出。def sort_by_freq(seq, key_builder, expandTrue): freq {} for x in seq: freq[x] freq.get(x, 0) 1 items sorted(freq.items(), keykey_builder) if expand: out [] for value, cnt in items: out.extend([value] * cnt) return out return [value for value, _ in items]这个函数把排序规则参数化了规则变化时只需要传不同的key_builder。我在做数据统计类的小工具时经常用这个结构比如统计日志里各接口的调用频次并按频次排序逻辑完全一致。把可变的规则和不变的流程分开是写代码时最值钱的一个习惯。题目会变流程很少变。6.2 复杂度心里得有数这道题的两种主流写法复杂度差异要能脱口而出写法时间复杂度空间复杂度适用场景双重循环暴力O(n²)O(n)n 小于 1000字典计数加排序O(n k log k)O(k)通用k 为不同值个数分桶按次数归并O(n V)O(n)次数范围小、值域集中数组下标计数O(n V)O(V)值域很小且非负其中 k 是不同数字的个数V 是值域大小。数组下标计数这个写法值得单独说一句如果题目保证数字范围在 0 到 1000 之间那把列表当桶用cnt[x] 1速度比字典快一个量级因为它省掉了哈希计算。代价是空间固定占用 V值域一大就不合适了。选哪种不是看哪个高级是看数据特征。值域小就用数组值域大就用字典这是最基本的一条。6.3 稳定性这个特性要用起来Python 的sorted是稳定排序这个特性在很多题里能省事。比如先按次级关键字排一遍再按主关键字排一遍两次稳定排序叠加结果等价于一次多关键字排序items sorted(freq.items(), keylambda kv: kv[0]) # 先按数值升序 items.sort(keylambda kv: kv[1], reverseTrue) # 再按次数降序第二次排序时次数相同的元素会保持第一次排序后的相对顺序也就是数值升序。这个技巧在处理主键降序、次键升序这种方向不一致的组合时特别好用因为它不需要取负也不受类型限制字符串一样适用。我个人的偏好是能一次 key 解决就用 key方向冲突不好处理时才用两趟稳定排序。两趟的写法可读性更好代价是多一次遍历通常在可接受范围内。7. 真实场景里这类排序比题目更刁钻7.1 并列规则往往没有写清楚刷题的时候规则是给定的做实际需求的时候规则经常是模糊的。比如要给一份词频统计做展示高频词优先这句话背后并列的时候到底按什么排按字母序按首次出现按业务权重如果需求方没说你随便选一个上线之后大概率要返工。我的做法是先把并列规则显式写出来跟对方确认一遍再动手。这个动作看着慢其实省时间因为改规则的成本远高于问一句的成本。7.2 数据量大了之后纯排序可能不是最优题目里 n 最多十万排序毫无压力。真实场景里如果有上千万条记录、几十万个不同值全量排序的开销就不容忽视了。这时候如果只需要前 100 名用堆更合适import heapq top heapq.nlargest(100, freq.items(), keylambda kv: (kv[1], -kv[0]))heapq.nlargest在 k 远小于 n 的时候复杂度是 O(n log k)比全排序的 O(n log n) 快得多。这个优化在题目里用不上但在做数据处理脚本时是常规操作。7.3 排序键里混入 None 会炸这道题的数据都是整数不会遇到这个问题。但实际数据里某个字段缺失是常态一旦 key 里出现NonePython 3 会直接抛TypeError因为None和整数不能比较。处理办法是在构造 key 的时候给默认值items sorted(freq.items(), keylambda kv: (-kv[1], kv[0] if kv[0] is not None else 0))这类防御性写法在刷题时显得多余在真实项目里是必需品。我现在写任何排序 key都会先想一遍这个字段会不会为空。7.4 数字精度问题如果数据里是浮点数排序本身没问题但用浮点数做字典的键会有精度陷阱。0.1 0.2 ! 0.3这种经典问题会导致本该合并的键被当成两个不同的键频次统计直接错掉。遇到浮点数据做频次统计我的处理是先按精度取整再统计比如统一保留两位小数转成整数处理。这个坑在题目里遇不到但在处理金额、比率这类数据时非常常见。8. 最后说几句实操上的体会这道题我前后写了四遍才彻底理顺第一遍暴力超时第二遍 Counter 并列出错第三遍输出长度搞错第四遍才把所有细节对齐。回头看真正难的地方从来不是怎么统计次数或者怎么排序而是那些题面没说透、样例测不出的边界条件。我的建议是刷这类题时多做一个动作自己造三组数据。一组正常数据验证主流程一组全并列数据验证次级关键字一组极端数据只有一个元素、全部相同、n 特别小验证边界。这三组跑通正确率能上一个台阶。另外元组排序加负号这个技巧值得专门花十分钟吃透。它不只是这道题的解法而是 Python 里处理多关键字排序的通用手法后面遇到任何主键降序、次键升序的需求都是同一套东西。真正把这一个点吃透比刷十道同类型的题收获更大。
数字次数排序这道题我第一眼扫过去的时候心里想的是送分题统计频次再排个序两行代码的事。结果真坐下来写从读入方式到并列项的次序再到输出格式前前后后被卡了不止一次。这道题出自蓝桥杯省赛Python组属于那种规则一句话、考点一大片的典型题目数字次数排序看着只是排序实际把哈希计数、多关键字排序、稳定性、输出格式这几件事一次性考全了。它适合两类人看一类是刚接触算法题、想把计数加排序这套组合拳打扎实的初学者另一类是刷过不少题但总在这种看着简单的题上丢分的老手。下面我按自己真实的解题顺序把这道题从规则拆解到代码落地再到各种变体和坑完整走一遍。1. 题面那一句话里藏着的三个考点1.1 把次数优先、数值兜底翻译成排序键原始题目的规则可以概括成一句话给一个长度为 n 的整数序列按每个数字出现的次数从多到少排序出现次数相同的数字按数值本身从小到大排序。这句话的信息密度其实很高。它明确给出了两级排序优先级第一级是出现次数方向是降序第二级是数字本身的值方向是升序。两级方向不一致这是很多人第一遍写错的地方——顺手写成keylambda x: (x[1], x[0])次数变成升序了样例一跑就露馅。再往下拆这句话还隐含了两件事。第一输出的到底是原序列重排还是每个不同的数字输出一次题目描述里通常写得比较含蓄我当时的做法是先看样例输出的长度如果输出长度等于 n那就是保留重复元素的重排如果输出长度等于不同数字的个数那就是去重后再排。第二出现次数这个信息本身要不要一起输出有些版本要求输出数字 次数的成对形式有些只输出数字。这两点如果判断错逻辑再对也是零分。所以拿到这类题我的固定动作是先花三十秒把输入是什么、输出是什么、输出多长三件事在纸上写清楚再动键盘。这不是啰嗦是我在省赛这种限时场景下用丢分换来的习惯。1.2 为什么出题人喜欢把这道题放在前面从命题角度想这道题放在省赛的前几题位置非常合理。它同时考察三种能力用字典做频次统计、用自定义 key 做多关键字排序、按格式输出结果。这三件事都是 Python 刷题的地基任何一项不牢都会在这里暴露。而且它有个好处——解法分层特别明显。会暴力的人能拿一部分分会字典的人能拿满分会Counter的人能写得更短但短不等于对Counter.most_common()在并列次数上的行为就让不少人栽过。题目简单但每一层都有细微差别这正是它的价值所在。1.3 数据规模决定了你能不能用暴力题目一般会给 n 的范围比如 n 不超过 10 万数值范围在某个区间内。这个信息必须看因为它直接决定算法选择。如果 n 是 1000 以内双重循环暴力统计完全没问题代码十行搞定。如果 n 到 10 万双重循环就是 100 亿次操作Python 里跑一天也出不来。我见过有人不看数据范围直接写暴力本地小样例跑得飞快一交上去大面积超时还以为是评测机的问题。这里有个经验看到 n 的数量级先在心里估一遍操作次数。Python 每秒大概能跑千万级别的简单操作10 万数据的 O(n log n) 排序毫无压力10 万数据的 O(n²) 就是灾难。这个心算习惯养成之后选解法的速度快很多。2. 三种写法从能跑到跑得快2.1 暴力统计思路最直白代价最昂贵最朴素的想法是对序列里每一个元素都完整扫一遍整个序列数它出现了几次然后带着这个次数去排序。def count_brute(nums): n len(nums) result [] for x in nums: cnt 0 for y in nums: if y x: cnt 1 result.append((x, cnt)) result.sort(keylambda p: (-p[1], p[0])) return result这段代码逻辑上没错样例也能过。问题在于它做了大量重复劳动——数字 7 出现了 50 次它就把数 7 的个数这件事重复做了 50 遍。整体复杂度是 O(n²)而且排序的 key 里带着重复的统计结果等于白算。我提这段不是为了让你用而是想说清楚为什么需要哈希表。哈希表的价值就在于把重复查询同一件事变成只算一次之后 O(1) 取用。理解了这一点后面所有写法都是自然推导出来的。2.2 字典计数加 sorted最稳的标准骨架标准解法分两步先用字典把每个数字的出现次数统计出来再对字典的键值对排序。import sys def solve(): data sys.stdin.read().split() if not data: return n int(data[0]) nums list(map(int, data[1:1 n])) freq {} for x in nums: freq[x] freq.get(x, 0) 1 items sorted(freq.items(), keylambda kv: (-kv[1], kv[0])) out [] for value, cnt in items: out.extend([str(value)] * cnt) print( .join(out))逐段说下为什么这么写。sys.stdin.read().split()一次性把全部输入读进来按空白切分这个写法对数据可能跨多行的情况天然免疫。有些题目样例里数字排成一行实际测试数据可能换行、可能有多余空格用input()逐行读再拼接容易出错用read().split()一劳永逸。freq.get(x, 0) 1是字典计数的经典写法比if x in freq判断少一次哈希查找代码也更紧凑。数据量大的时候这个细节能省一点时间。排序的 key 是(-kv[1], kv[0])。这里用了个小技巧次数取负把降序问题转成升序问题。因为 Python 的排序默认是升序而元组比较是从左到右逐项比所以-cnt小的排在前面等价于 cnt 大的排在前面cnt 相同时再比 valuevalue 小的在前。这一行是整个解法的核心。最后输出部分out.extend([str(value)] * cnt)是把每个数字按它的出现次数展开。这一步对应输出原序列重排的版本。如果题目要求去重输出就把这个循环换成out.append(str(value))即可。2.3 Counter 的甜头与它埋的雷collections.Counter是 Python 处理频次统计的利器一行就能完成计数from collections import Counter freq Counter(nums) items freq.most_common()很多人的第一反应是most_common()出来就是答案直接输出。这里必须踩一脚刹车。most_common()的语义是按计数从大到小返回对于计数相同的元素它不保证按数值大小排序。源码层面当不传参数时它内部走的是sorted(self.items(), key_itemgetter(1), reverseTrue)而 Python 的 sorted 是稳定排序稳定意味着相等的元素保持原有顺序——原有顺序是什么是元素第一次被插入 Counter 的顺序也就是在原序列中首次出现的位置。所以如果你的输入是5 5 3 3 9most_common()给出的并列项顺序取决于 5 和 3 谁先出现跟数值大小没关系。这种错误特别隐蔽因为样例有时候恰好顺序对上了你根本发现不了。稳妥的写法是把most_common()的结果再接一次排序items sorted(freq.items(), keylambda kv: (-kv[1], kv[0]))绕了一圈回到同一个 key 函数上。所以我的建议是这道题直接用 sorted 加自定义 key别贪 Counter 那一行的方便。除非你确定规则里没有并列时的次序要求。提示如果确实想用 Counter 又要处理并列可以写sorted(freq.items(), keylambda kv: (-kv[1], kv[0]))等价于先 most_common 再按值稳定排一次但没必要绕。3. 排序键的三种造法各有各的适用面3.1 元组加负号最省事也最常用前面用的(-cnt, value)是这道题的最优写法简短、无依赖、速度快。它的适用前提是所有参与排序的字段都能取负也就是必须是数值类型。这个前提在本题里成立因为次数一定是正整数数值也是整数。但如果题目改成按字符串字典序-x[0]就直接报错了。所以这个技巧不是万能的用之前先确认类型。顺带说一个细节(-cnt, value)里的负号是作用于整个字段不是作用于排序结果。有人会写成keylambda kv: (kv[1], kv[0])然后加reverseTrue那就变成次数降序、数值也降序了第二级关键字方向反了。这种错误在检查的时候很难一眼看出来因为次数部分是对的。3.2 cmp_to_key能表达任意规则但慢Python 3 的 sorted 只接受 key 函数不接受比较函数。如果规则复杂到没法用一个 key 元组表达就得请出functools.cmp_to_keyfrom functools import cmp_to_key def cmp(a, b): if a[1] ! b[1]: return -1 if a[1] b[1] else 1 return -1 if a[0] b[0] else (0 if a[0] b[0] else 1) items sorted(freq.items(), keycmp_to_key(cmp))这段代码跑起来是对的但它的常数因子比 key 版本大好几倍因为每次比较都要调用一次 Python 函数而 key 版本只在对每个元素求 key 时调用一次。数据量上万的时候差距就明显了。我的原则是能用 key 表达就绝不写 cmp。这道题的规则用元组完全能表达cmp_to_key 属于知道有这么个东西就够了。3.3 先分桶再拼接绕开排序的思路还有一种思路值得提一句虽然不是主流。既然次数的取值范围只可能是 1 到 n那就可以按次数分桶from collections import defaultdict buckets defaultdict(list) for value, cnt in freq.items(): buckets[cnt].append(value) out [] for cnt in sorted(buckets.keys(), reverseTrue): for value in sorted(buckets[cnt]): out.extend([str(value)] * cnt)这个写法把两级排序拆成外层按次数降序、内层按数值升序逻辑非常清晰特别适合次数范围小、数值分布集中的场景。缺点是代码长、常数开销大本题用不上。但如果是按出现次数分组输出这种变体题分桶的思路反而更自然。我把这个写出来是想说同一道题不该只有一种写法。当你把规则理解透了代码只是表达方式的选择反过来如果只会背一种模板规则一改就傻眼。4. 我在调试这道题时踩的六个坑4.1 输入没读完就开始算最开始的版本我是这么写的n int(input()) nums list(map(int, input().split()))本地样例一跑对了。交上去错了。原因很简单测试数据的 n 个数字未必挤在一行里可能是三行、五行甚至中间夹空行。input()只读一行后面的数据全丢。正确做法是全部读进来再切data sys.stdin.read().split() n int(data[0]) nums list(map(int, data[1:1 n]))注意data[1:1 n]这个切片它保证即使输入里有多余的内容也只取前 n 个防止脏数据混进统计。4.2 该去重的时候没去重这一步的错误方向有两个都很常见。方向一题目要求每个数字只输出一次你却按次数展开成了原序列长度。方向二题目要求输出完整重排序列你却只输出了不同的数字。判断依据只有一个——看样例输出。如果样例输入的 n 是 8输出也是 8 个数那就是保留重复如果输出只有 4 个数那就是去重。我的笨办法是写代码之前在注释里写一行# 输出长度 n 还是 不同数字个数跑完样例先核长度长度对了再看内容。这个动作花不了三秒但能挡掉一大类错误。4.3 次数降序写成了升序keylambda kv: (kv[1], kv[0])和keylambda kv: (-kv[1], kv[0])只差一个负号肉眼几乎看不出来但输出结果完全不同。排查方法很直接造一个次数差异明显的测试数据比如[1,1,1,2,2,3]正确的输出应该以三个 1 开头。如果开头是 3说明方向反了。养成自己造一组能区分方向的数据的习惯比盯着代码看十分钟管用。4.4 负数和零的处理如果题目里的数字可以取负(-cnt, value)这个写法依然成立因为负号作用在次数上跟数值本身的正负无关。但要注意另一件事数值排序的方向。规则说的是数值从小到大那 -5 就应该排在 3 前面Python 的默认整数比较正好是这个语义不需要特殊处理。真正容易出问题的是用字符串做键的场景。10 9在字符串比较下是 True因为逐字符比的时候 1 9。如果你的数字被当作字符串处理排序结果会完全错乱。所以只要题目没说按字典序就老老实实转 int。4.5 Counter.most_common 的并列顺序前面提过这里再强调一次因为它真的太容易中招。most_common()在计数相同时按插入顺序返回插入顺序又取决于元素在输入里的首次位置。输入顺序一变输出就变而样例往往看不出这个问题。我当时的排查过程是这样的先本地跑通样例再自己造了一组并列数据发现输出顺序和预期不符然后去查most_common的行为才意识到问题。这个链路值得记住——样例过了不代表对一定要造边界数据。4.6 输出格式的细节print( .join(out))是最常见的输出方式。但有两处坑。第一处如果out是空的比如 n 为 0 或者数据异常 .join([])返回空字符串print出来是一个空行某些评测机对空行是敏感的。稳妥的做法是加个判断。第二处如果题目要求每个数字一行那就得用\n.join(out)。这个不能靠猜必须看题面的输出说明。我整理了一张排查表遇到错误时可以对着过一遍现象最可能的原因定位方法部分测试点通过部分超时用了 O(n²) 暴力统计看 n 的范围改字典计数全部答案错误但格式正常次数排序方向反了造[1,1,1,2,2,3]验证并列项顺序不对用了 most_common 未二次排序造次数相同的两组数据输出长度不对去重与展开搞混了对比样例输出长度运行时报错 IndexError输入切片越界或数据不足打印 data 长度核对数字顺序错乱像字符排序键里混入了字符串检查是否漏了 int 转换5. 规则一改代码该往哪儿动5.1 次数相同按数值从大到小这是最常见的变体。改动只在排序键上把kv[0]换成-kv[0]。items sorted(freq.items(), keylambda kv: (-kv[1], -kv[0]))两个字段都取负整个排序就变成次数降序、数值降序。如果数值可能很大又不想取负也可以写成两级显式判断但元组加负号更简洁。这类改动看起来微不足道但它揭示了一个重要认知多关键字排序的本质是把多个比较维度编码进一个可比较的对象里。只要你能构造出这个对象规则怎么变都能应对。5.2 次数相同按首次出现位置这个变体在真实业务里比按数值排序更常见。比如统计热搜词同样热度的词应该按上榜时间先后展示而不是按词本身的编码排。实现方法是记录每个数字第一次出现的位置first_pos {} for i, x in enumerate(nums): if x not in first_pos: first_pos[x] i items sorted(freq.items(), keylambda kv: (-kv[1], first_pos[kv[0]]))这里 key 函数里引用了外部的first_pos字典闭包捕获完全合法。注意if x not in first_pos只在首次出现时写入后面的重复出现不会覆盖这正是我们要的语义。5.3 按字符串字典序排有些题目的输入直接就是字符串比如统计字符出现次数。这时候数字转字符串的坑就来了10排在9前面。如果题目确实要求字典序那就照做但要在心里明确这是字典序不是数值序。如果题目说的是按大小那就必须先转成数字再排。判断依据还是题面用词字典序、ASCII 顺序是一个意思数值大小、从小到大是另一个意思。items sorted(freq.items(), keylambda kv: (-kv[1], kv[0])) # 如果 kv[0] 是字符串这里就是字典序5.4 只输出出现次数前 k 的数字这是把题目往 Top-K 方向延伸。改动点有两处排序之后做切片以及处理第 k 名出现并列的情况。items sorted(freq.items(), keylambda kv: (-kv[1], kv[0])) k 3 result items[:k]如果要求并列第 k 名全部输出就不能简单切片得先取第 k 名的次数阈值再把所有达到阈值的挑出来if len(items) k: threshold items[k - 1][1] result [it for it in items if it[1] threshold]这两种语义在实际场景里差别很大题目怎么说就怎么实现别自作主张。6. 从这道题里能带走的通用套路6.1 计数加排序的模板可以固化下来把这道题的骨架抽出来其实是一个很通用的模式遍历一次建频次表再对频次表的多关键字排序最后按规则展开输出。def sort_by_freq(seq, key_builder, expandTrue): freq {} for x in seq: freq[x] freq.get(x, 0) 1 items sorted(freq.items(), keykey_builder) if expand: out [] for value, cnt in items: out.extend([value] * cnt) return out return [value for value, _ in items]这个函数把排序规则参数化了规则变化时只需要传不同的key_builder。我在做数据统计类的小工具时经常用这个结构比如统计日志里各接口的调用频次并按频次排序逻辑完全一致。把可变的规则和不变的流程分开是写代码时最值钱的一个习惯。题目会变流程很少变。6.2 复杂度心里得有数这道题的两种主流写法复杂度差异要能脱口而出写法时间复杂度空间复杂度适用场景双重循环暴力O(n²)O(n)n 小于 1000字典计数加排序O(n k log k)O(k)通用k 为不同值个数分桶按次数归并O(n V)O(n)次数范围小、值域集中数组下标计数O(n V)O(V)值域很小且非负其中 k 是不同数字的个数V 是值域大小。数组下标计数这个写法值得单独说一句如果题目保证数字范围在 0 到 1000 之间那把列表当桶用cnt[x] 1速度比字典快一个量级因为它省掉了哈希计算。代价是空间固定占用 V值域一大就不合适了。选哪种不是看哪个高级是看数据特征。值域小就用数组值域大就用字典这是最基本的一条。6.3 稳定性这个特性要用起来Python 的sorted是稳定排序这个特性在很多题里能省事。比如先按次级关键字排一遍再按主关键字排一遍两次稳定排序叠加结果等价于一次多关键字排序items sorted(freq.items(), keylambda kv: kv[0]) # 先按数值升序 items.sort(keylambda kv: kv[1], reverseTrue) # 再按次数降序第二次排序时次数相同的元素会保持第一次排序后的相对顺序也就是数值升序。这个技巧在处理主键降序、次键升序这种方向不一致的组合时特别好用因为它不需要取负也不受类型限制字符串一样适用。我个人的偏好是能一次 key 解决就用 key方向冲突不好处理时才用两趟稳定排序。两趟的写法可读性更好代价是多一次遍历通常在可接受范围内。7. 真实场景里这类排序比题目更刁钻7.1 并列规则往往没有写清楚刷题的时候规则是给定的做实际需求的时候规则经常是模糊的。比如要给一份词频统计做展示高频词优先这句话背后并列的时候到底按什么排按字母序按首次出现按业务权重如果需求方没说你随便选一个上线之后大概率要返工。我的做法是先把并列规则显式写出来跟对方确认一遍再动手。这个动作看着慢其实省时间因为改规则的成本远高于问一句的成本。7.2 数据量大了之后纯排序可能不是最优题目里 n 最多十万排序毫无压力。真实场景里如果有上千万条记录、几十万个不同值全量排序的开销就不容忽视了。这时候如果只需要前 100 名用堆更合适import heapq top heapq.nlargest(100, freq.items(), keylambda kv: (kv[1], -kv[0]))heapq.nlargest在 k 远小于 n 的时候复杂度是 O(n log k)比全排序的 O(n log n) 快得多。这个优化在题目里用不上但在做数据处理脚本时是常规操作。7.3 排序键里混入 None 会炸这道题的数据都是整数不会遇到这个问题。但实际数据里某个字段缺失是常态一旦 key 里出现NonePython 3 会直接抛TypeError因为None和整数不能比较。处理办法是在构造 key 的时候给默认值items sorted(freq.items(), keylambda kv: (-kv[1], kv[0] if kv[0] is not None else 0))这类防御性写法在刷题时显得多余在真实项目里是必需品。我现在写任何排序 key都会先想一遍这个字段会不会为空。7.4 数字精度问题如果数据里是浮点数排序本身没问题但用浮点数做字典的键会有精度陷阱。0.1 0.2 ! 0.3这种经典问题会导致本该合并的键被当成两个不同的键频次统计直接错掉。遇到浮点数据做频次统计我的处理是先按精度取整再统计比如统一保留两位小数转成整数处理。这个坑在题目里遇不到但在处理金额、比率这类数据时非常常见。8. 最后说几句实操上的体会这道题我前后写了四遍才彻底理顺第一遍暴力超时第二遍 Counter 并列出错第三遍输出长度搞错第四遍才把所有细节对齐。回头看真正难的地方从来不是怎么统计次数或者怎么排序而是那些题面没说透、样例测不出的边界条件。我的建议是刷这类题时多做一个动作自己造三组数据。一组正常数据验证主流程一组全并列数据验证次级关键字一组极端数据只有一个元素、全部相同、n 特别小验证边界。这三组跑通正确率能上一个台阶。另外元组排序加负号这个技巧值得专门花十分钟吃透。它不只是这道题的解法而是 Python 里处理多关键字排序的通用手法后面遇到任何主键降序、次键升序的需求都是同一套东西。真正把这一个点吃透比刷十道同类型的题收获更大。
