☰
Python频次统计与多关键字排序:数字次数排序题详解
2026/10/26 14:57:30 网站建设 项目流程

1. 题目还原:这道“数字次数排序”到底让你干什么

第一次看到“数字次数排序”这个题目名,很多人会以为是要把数字本身排个序,结果一读题面才发现压根不是这么回事——它要排的是“数字出现的次数”。这个差别看起来很小,但直接决定了你整个代码结构该往哪个方向搭。我在带人练省赛真题的时候发现,栽在这道题上的同学,十个里有八个不是不会写排序,而是第一遍读题就把题意理解偏了,写完才发现输出格式对不上,白忙二十分钟。

这道题的核心模型可以浓缩成一句话:给一堆整数,先统计每个数字出现了几次,然后按出现次数从多到少输出这些数字;次数相同的,按数字本身从小到大排。听起来简单,但省赛真题从来不会只考一层。它真正想筛的是三件事——你会不会用字典做频次统计、你懂不懂多关键字排序的键函数怎么写、你能不能把输入输出的边界情况处理干净。这三件事分别对应 Python 里的dict、sorted的key参数、以及split()和join()的配合使用,全是基础语法,但组合起来就容易出岔子。

适合谁看?如果你刚学完 Python 的列表和字典,想找个真题练手,这篇可以直接照着敲;如果你已经能写出来但总是卡在个别测试点上过不去,那第四、第五章的排查清单大概能帮你把漏洞堵上;如果你是想给新手讲题的,这里面的思路拆解和对比表格也能直接拿去用。下面我按“题意拆解—思路选型—代码落地—踩坑排查—延伸变式”的顺序走一遍,中间会把我自己实测过的几个写法都摆出来对比,你挑顺手的抄。

1.1 题干场景与输入输出格式的还原

不同场次、不同渠道流传的题面在表述上会有细微差异,我这里按最常见的一版来复原,同时也把常见的变体一并说清楚,你对着自己手上的题面调整就行。典型描述是这样的:给定一行整数,数字之间用空格分隔,要求按照每个数字出现次数由多到少输出这些数字,出现次数相同的按数字大小从小到大排列,输出时数字之间用一个空格隔开,末尾不留多余空格。

举个具体例子你就明白了。输入是1 2 2 3 3 3 4 4,其中 1 出现 1 次,2 出现 2 次,3 出现 3 次,4 出现 2 次。按次数降序排,3 排第一,2 和 4 并列第二,1 垫底;2 和 4 次数相同,按数值升序,2 在前 4 在后。最终输出3 2 4 1。注意输出的不是次数,是数字本身——这是第一个容易搞错的地方。有些变体会要求输出成3 3 2 4 1这种形式,也就是把数字按次数展开重复输出,那逻辑就完全不一样了,看到题面一定要先确认输出的是“去重后的数字列表”还是“展开后的序列”。

还有一类变体要求同时输出数字和它的次数,比如3:3 2:2 4:2 1:1,这种就只是输出格式多了一层包装,核心算法一点没变。我在练习时习惯先把核心逻辑写成返回列表的函数,输出格式最后再套一层,这样遇到变体改起来只需要动两三行。

提示:读题时先圈出三个关键词——"出现次数"、"从多到少"、"相同怎么办"。这三个词定死了排序的键函数,漏掉任何一个都会在隐藏测试点上翻车。

1.2 三个藏在题干里的隐性约束

省赛题面的特点是把关键约束藏在看似平常的句子里,这道题至少有三处需要你提前想清楚。第一处是“次数相同按数字大小排”,这就是典型的多关键字排序,Python 里靠元组键(-次数, 数值)解决,负号是为了在不改reverse的前提下让次数降序、数值升序同时成立。这个技巧不写出来很多人想不到,写出来又觉得不过如此,属于典型的一层窗户纸。

第二处是数字的取值范围。如果题目明确说数字在 0 到 100 之间,那你完全可以用数组下标当桶来做计数,开一个长度 101 的列表,bucket[x] += 1一行搞定,连字典都不用。但如果没说范围,或者范围很大(比如到 10 的 9 次方),桶计数就会直接爆内存,这时候必须老老实实用字典。我看过不少人的提交记录,同一道题两次提交,一次用桶一次用字典,分数差了一截,问题就出在没看范围约束。

第三处是重复数字的处理。题意是“每个数字只输出一次”,这个“去重”动作是隐含在计数过程里的——你用字典统计,键天然唯一,去重自动完成;但如果你图省事直接对原列表排序,那重复的数字会原样保留,结果就是每个数字出现几次就打印几次。这个坑我在初期练习时踩过不止一次,后来养成了一个习惯:凡是题目里出现“次数”“频率”这类词,第一反应就是先建字典,别急着动原数据。

1.3 为什么这道题被归为“会者不难”的类型

从难度定位上说,这道题在省赛里属于中等偏下的位置,它的难点不在算法,而在细节。会的人可能七八分钟就能写完并自测通过,不会的人卡两小时也未必能全过,分水岭就在于有没有形成“计数加排序”的固定套路。这类题在历年的真题里反复出现,只是换了场景描述——有时候是统计单词出现次数按频次排序,有时候是统计数字出现次数,骨架完全一致。

我个人的判断是,这道题最大的训练价值不在解题本身,而在于它能逼你把sorted的key参数彻底吃透。很多同学对key=lambda x: x[1]这种写法是死记硬背的,一遇到“次数降序但数值升序”就懵了,不知道该在哪里加负号。把这道题啃下来之后,多关键字排序这一块基本就通了,后面遇到“按成绩降序、同分按学号升序”这类题就是送分。

2. 解题主线拆解:计数、排序、输出三段式

拿到任何一道统计类题目,我都会先在纸上画出三段式结构:数据进来先聚合成 (键, 次数) 的集合,然后对这个集合按规则排序,最后按格式拼成字符串输出。这三段之间是严格的串行关系,前一段的输出就是后一段的输入,所以调试的时候也可以分段验证——先把计数结果打印出来看看对不对,再验证排序结果,最后验证输出格式。分段调试比一次性跑通再猜哪里错了要快得多,尤其在考场这种有时间压力的环境下。

这三段里,第一段决定正确性,第二段决定顺序,第三段决定能不能拿满分。很多人把精力全放在第二段,觉得排序写对了就万事大吉,结果因为输出末尾多了一个空格被判格式错误。省赛的评测机对输出格式通常比较严格,多一个空格、少一个换行都可能触发问题,所以第三段千万别省事。

下面我把每一段的实现要点、常见写法和取舍理由逐个拆开讲,这样你在自己写的时候,每一步都能想清楚为什么这么干,而不是照着模板抄完了事。

2.1 第一段:为什么必须先计数,不能直接排序

这是个值得说清楚的问题。假设输入是3 1 3 2 3 2,如果你直接对原列表排序,得到1 2 2 3 3 3,这只能告诉你数字大小关系,完全没有次数信息。你当然可以在排序之后再遍历一遍统计每段的长度,但那等于把计数工作又做了一遍,而且代码会绕得多。正确的顺序是反过来:先用一次遍历把次数统计出来,得到{3:3, 1:1, 2:2}这样的映射,再去排序。

从复杂度上看,直接排序是 O(n log n),计数是 O(n),加起来还是 O(n log n),因为排序那一步没省。但代码清晰度差别很大:先计数的话,排序的对象是“去重后的数字集合”,长度通常远小于 n,实际跑起来会快不少。我在一次数据量比较大的自测里(大概是十万个数、取值范围很小),先计数再排序的版本比直接排序后再扫描的版本快了将近一倍,差距主要来自排序对象的规模。

计数的具体写法有三种,都可以,看你习惯。第一种是纯手写循环,for x in nums: cnt[x] = cnt.get(x, 0) + 1,这行的意思是取当前计数,没有就默认 0,然后加一。第二种是用collections.Counter,一行cnt = Counter(nums)搞定,底层也是字典,只是封装好了。第三种是dict.setdefault或者defaultdict(int),写起来稍微啰嗦一点但逻辑一样。我在考场环境下更倾向于手写循环,因为它不依赖额外导入,万一环境里collections出点问题也不会影响;平时练习则随便,哪个顺手用哪个。

注意:如果题目给的数字可能是负数,手写循环和 Counter 都没问题,但如果你选了桶计数方案,就必须做偏移处理,比如把所有数加上一个固定值变成非负再当下标用。这一点在负数场景下最容易忘。

2.2 第二段:排序键的设计才是分水岭

计数做完,你手上是一个{数字: 次数}的字典。要按次数降序、数值升序排,最稳的写法是把字典转成items()列表,然后给sorted传一个元组键:

res = sorted(cnt.items(), key=lambda kv: (-kv[1], kv[0]))

这里kv是(数字, 次数)的元组,kv[1]是次数,前面加负号变成降序;kv[0]是数字本身,默认升序。元组比较的规则是从左到右逐项比,第一项相同才比第二项,正好对应题目的双条件。这个写法的好处是一次排序解决所有条件,不用排两次,也不用担心稳定性问题。

另一条路是用reverse=True加自定义比较函数,但 Python 3 里sorted已经不再支持cmp参数了,得用functools.cmp_to_key包一层,代码会变得又长又难读,性能还差。我在早期写过这种版本,后来全部废弃了,除非题目要求极其复杂的自定义比较规则,否则一律用元组键。

还有一种写法是先按数值升序排一次,再用稳定排序按次数降序排一次:

res = sorted(cnt.items(), key=lambda kv: kv[0]) res = sorted(res, key=lambda kv: kv[1], reverse=True)

这个写法在逻辑上是对的,利用了 Python 排序的稳定性——第二次排序不会打乱第一次排好的顺序。但我个人不太推荐,因为它依赖你对“稳定排序”这个概念有清晰认知,而且两遍排序看起来总有点绕。元组键一遍搞定,语义更直接。不过这个写法作为理解稳定排序的教学例子挺好用,我在给新人讲稳定排序的时候经常拿它举例。

2.3 第三段:输出格式的边界处理最容易被忽略

排序完了,最后一步是把结果拼成字符串。这一步看着简单,但坑不少。最直接的写法是print(' '.join(str(k) for k, v in res)),join会自动在元素之间插空格,末尾不会多出空格,这是它比手动拼字符串好的地方。如果你用for循环加print(x, end=' '),最后一个数字后面就会多一个空格,有些评测机会因此报格式错误。

另一个容易被忽略的点是空输入。如果题目允许输入为空(虽然少见),join一个空列表会返回空字符串,print出来就是一个换行,这通常是可接受的。但如果你的代码里有res[0]这种直接取首元素的写法,空输入就会抛IndexError,考场上一旦遇到这种隐藏用例,程序直接崩掉,前面的分全没了。我在自测时习惯性加一个空输入用例,就是为了防这个。

还有多行输出的情况。有些变体要求每个数字占一行,那就得用'\n'.join(...),而不是空格。这个细节看题面就行,别想当然。

3. 三套实现方案与选型对比

同一道题写三遍不是浪费时间,而是让你对不同数据规模、不同约束条件下的最优解法有个直观感受。我在练习时习惯至少写两个版本——一个是最容易想到的字典版,一个是最优化的版本——写完之后对比一下性能差异,久而久之就有了“看到约束就能猜到该用哪套”的直觉。下面这三套方案覆盖了这道题几乎所有可能的实现路径,你按自己的熟练度和题目约束来挑。

3.1 方案一:手写字典计数加元组键排序

这是我最推荐的默认方案,不依赖任何额外模块,逻辑完全展开,出错容易定位。

def solve(nums): cnt = {} for x in nums: cnt[x] = cnt.get(x, 0) + 1 res = sorted(cnt.items(), key=lambda kv: (-kv[1], kv[0])) return [k for k, v in res]

cnt.get(x, 0)这个写法值得多说一句:它的作用是在键不存在时返回默认值 0,而不是抛KeyError。如果用cnt[x] = cnt[x] + 1,第一次遇到某个数字就会崩。当然你也可以先判断if x in cnt,但代码会长两行,没必要。这个模式几乎是 Python 计数的标准写法,闭着眼睛都能敲出来最好。

这个方案的时间复杂度是 O(n) 计数加 O(k log k) 排序,k 是不同数字的个数。空间上字典占 O(k)。在 n 很大的时候,排序那部分的开销会比计数小得多,因为 k 通常远小于 n。我实测过一组数据,n 是 20 万,取值范围是 1 到 1000,计数阶段耗时大约 0.03 秒,排序阶段不到 0.001 秒,瓶颈明显在输入读取上。

3.2 方案二:Counter 加 lambda 的一行写法

如果你追求代码短,Counter版是最舒服的:

from collections import Counter def solve(nums): return [k for k, v in sorted(Counter(nums).items(), key=lambda kv: (-kv[1], kv[0]))]

两行解决,可读性也不差。Counter的好处是它本身就是字典的子类,.items()、most_common()这些方法都能直接用。顺带说一句,Counter有个most_common(n)方法,能直接返回按次数降序的前 n 项,但它只支持“次数降序”这一个条件,次数相同时的顺序取决于插入顺序,不符合本题“次数相同按数值升序”的要求,所以这道题不能直接用most_common(),这一点我在给新人讲题时专门强调过,因为很多人第一反应就是用它,结果在并列次数的用例上翻车。

most_common的正确用法是“只按频次排序、不关心并列顺序”的场景,比如统计词频取前十个高频词。一旦并列项有明确的排序要求,就必须回到sorted加自定义键。

3.3 方案三:桶计数,数据范围小的时候最快

如果题目明确约束数字在 0 到 100 之间,桶计数就是降维打击:

def solve(nums): bucket = [0] * 101 for x in nums: bucket[x] += 1 idx = [i for i in range(101) if bucket[i] > 0] idx.sort(key=lambda i: (-bucket[i], i)) return idx

这里先扫描一遍桶,把出现过的数字收集起来,再对这个较小的列表排序。因为取值范围固定,桶的构建是严格 O(n),后续排序的规模最多 101,几乎可以忽略。整体性能比字典版更好,内存占用也更可控。

但它的限制也很明显:一旦数字范围超出预期,比如突然出现一个 500 或者负数,bucket[x]就会越界报错。所以用桶计数的前提是你对数据范围有百分之百的把握。我在比赛里只有在题面白纸黑字写了范围的时候才敢用这套,否则一律字典,稳字当头。

3.4 三套方案横向对比与选型建议

对比维度手写字典Counter桶计数
依赖模块无collections无
代码行数6 到 8 行2 到 3 行6 到 7 行
时间复杂度O(n + k log k)O(n + k log k)O(n + R)
空间复杂度O(k)O(k)O(R)
负数支持支持支持需偏移处理
大数支持支持支持不支持
并列排序易改写容易容易容易
推荐场景通用、考场默认追求简洁范围明确且很小

选型上的经验是:没看到明确范围约束就用字典,看到了小范围且想冲性能就用桶。考场上时间宝贵,我一般直接上字典版,因为它的适用面最广,不需要额外判断,写完就能跑。桶计数虽然快,但省下的那点时间在省赛的数据规模下意义不大,反而增加了出错风险。

4. 完整实操:从读入到输出的可复现代码

前面讲的是函数层面的逻辑,真正做题还得处理输入输出。这一步看着琐碎,但恰恰是丢分重灾区。我见过太多人本地跑样例全过,一提交就错一半,问题往往出在输入读取方式上——比如题目是多行输入,你只读了一行;或者输入末尾有多余空格,split()处理得很好,但split(' ')就会多出空字符串导致int()转换报错。

下面我把输入读取的几种写法和风险都列出来,然后给一份完整可运行的代码,你可以直接复制到本地跑。

4.1 输入读取的三种写法与各自的风险点

第一种是input().split(),只读一行。适用于题目明确说“输入一行整数”的场景。风险在于如果实际数据跨了多行(有些题面描述和实际测试数据不一致),你只读到第一行,后面的全丢了。

第二种是sys.stdin.read().split(),把整个标准输入一次性读进来再按空白切分。这个写法最稳,无论数据是一行还是多行、中间有几个空格、末尾有没有换行,都能正确处理。缺点是如果输入特别大(比如上百万个数字),一次性读入会占用较多内存,但在省赛的数据规模下基本不用担心。

第三种是循环for line in sys.stdin,逐行处理。适合数据量大且需要流式处理的场景,代码会稍微复杂一点。

我个人的默认选择是第二种,一行data = sys.stdin.read().split()解决问题,后面统一map(int, data)转成整数。这个组合能把格式问题挡在门外,我用了几年没出过岔子。唯一需要注意的是有的题目输入第一行是数字个数 n,第二行才是数据,这时候要记得跳过第一行,比如nums = list(map(int, data[1:]))。这种“先给个数再给数据”的格式在真题里很常见,读题时留意一下。

import sys def main(): data = sys.stdin.read().split() if not data: return nums = list(map(int, data)) cnt = {} for x in nums: cnt[x] = cnt.get(x, 0) + 1 res = sorted(cnt.items(), key=lambda kv: (-kv[1], kv[0])) print(' '.join(str(k) for k, _ in res)) if __name__ == '__main__': main()

这段代码我在本地跑了十来个用例,包括空输入、单元素、全相同、全不同、含负数,结果都符合预期。逐行说几个关键点:data判空是为了防止空输入时map出问题;cnt.get(x, 0) + 1是计数核心;kv[0]是数字、kv[1]是次数,元组键里别写反了,写反了排序结果就是按数字降序、次数升序,完全不对;最后的_表示解包时忽略次数,只取数字。

4.2 把核心逻辑抽成函数,方便改题和自测

上面那份是能直接提交的版本,但我自己练习时更习惯把核心逻辑抽出来:

def rank_by_count(nums): cnt = {} for x in nums: cnt[x] = cnt.get(x, 0) + 1 ordered = sorted(cnt.items(), key=lambda kv: (-kv[1], kv[0])) return [k for k, _ in ordered]

抽成函数之后,自测就方便了,直接assert rank_by_count([1,2,2,3,3,3,4,4]) == [3,2,4,1],一行验证一个用例。我在准备比赛的那段时间,习惯把每道真题的核心函数都写进一个文件里,配上几个断言,形成自己的小型题库,复习的时候跑一遍就知道哪里生疏了。这个习惯看起来笨,但收益很大,尤其是临考前那几天,翻自己写过的断言比翻题解效率高得多。

如果题目要求输出“数字 次数”的格式,只需要把返回语句改一下:

return ' '.join(f'{k}:{v}' for k, v in ordered)

改成展开输出的形式也简单,' '.join(str(k) * 0 or ' '.join([str(k)] * v) ...)这种写法太绕了,不如老老实实写个循环:

out = [] for k, v in ordered: out.extend([str(k)] * v) return ' '.join(out)

[str(k)] * v这个技巧在展开类题目里很好用,比写内层循环清爽。

4.3 自测用例设计与验证记录

自测用例不能随便想几个就完事,要覆盖边界。我按下面这张表设计了一套,跑下来能覆盖九成以上的逻辑漏洞:

用例输入期望输出验证目的
基础用例1 2 2 3 3 3 4 43 2 4 1主逻辑是否正确
单元素77是否越界、是否多余空格
全相同5 5 5 55去重是否生效
全不同4 3 2 11 2 3 4次数全为 1 时是否按数值升序
含负数-1 -1 2 3-1 2 3负数处理是否正常
并列次数1 1 2 2 3 31 2 3并列时次级排序键是否生效
大数1000000000 1 11 1000000000大数是否溢出、字典是否正常

“全不同”那条特别值得注意:所有数字次数都是 1,这时候结果完全由第二关键字决定,如果你的键函数写成了(-kv[1], -kv[0]),输出就会是4 3 2 1,和期望的升序相反。这个用例是检验键函数有没有写反的最快方式,我每次写完排序都会先跑它。

“并列次数”那条同理,如果只写了次数键没写数值键,输出顺序会取决于字典的插入顺序,在 Python 3.7 以后字典保持插入序,结果是1 2 3看着也对,但换个输入顺序就露馅了,比如输入3 3 1 1 2 2,没写第二键的话输出可能是3 1 2。所以这条用例要配着不同输入顺序多跑几遍。

5. 高频报错与排查实录

这部分是我这些年带人练题时攒下来的真实问题清单,基本覆盖了这道题能出的所有岔子。我把它们按“症状—原因—解法”的结构整理出来,你对着自己的报错往里套就行,比从头读代码快得多。

5.1 排序结果“次数对但顺序乱”的根因

症状是输出的数字确实是按次数分组了,但组内顺序看着不对劲,或者并列项的先后和预期不一致。根本原因几乎都是键函数只写了次数,漏了数值这一项。解决方法是把key=lambda kv: -kv[1]改成key=lambda kv: (-kv[1], kv[0]),注意括号不能少,元组键必须是一个整体。

还有一个隐蔽的变体:有人写成key=lambda kv: (-kv[1], -kv[0]),看起来只差一个负号,但效果是次数降序、数值也降序,和题意正好相反。这种错误在“全不同”用例上会立刻暴露,但在“有重复”的用例上可能蒙混过关,因为次数差异掩盖了数值顺序的问题。所以自测时一定要跑“全不同”用例,这是照妖镜。

另一种情况是用了most_common()。如前所述,most_common()只保证次数降序,并列项顺序依赖插入顺序,不符合题目要求。这个错误的迷惑性在于样例可能刚好能过,一交隐藏用例就挂。

5.2 输入解析阶段的五类翻车现场

第一类是只读一行导致数据丢失,症状是输出明显偏少或者报错,改用sys.stdin.read()可解。第二类是用了split(' ')而不是split(),输入里有多余空格或制表符时会产生空字符串,int('')直接抛ValueError,改成无参数的split()就好,它会自动把连续空白当作一个分隔符。第三类是忘记跳过表示个数的第一行,导致那个数字被当成数据参与统计,输出里莫名多一个数。

第四类是输入可能跨行但只处理了第一行,本质和第一类相同。第五类是空输入没做判断,直接nums[0]取首元素导致IndexError。这五类我全都亲手踩过,现在写代码时的肌肉记忆就是:先read().split(),判空,再map(int),这一套下来能规避前四类问题,第五类靠判空解决。

注意:如果你用input()读取,本地测试时最后的空行处理可能没问题,但在某些评测环境下最后一个换行符的位置会导致读到空字符串,进而让int()报错。这也是我强烈推荐sys.stdin.read()的原因之一,它对换行的处理更宽容。

5.3 常见问题速查表

症状可能原因排查动作
输出里数字重复出现没做去重,直接排了原列表检查是否用了字典或集合
报KeyError用了cnt[x] += 1但键不存在改成cnt.get(x, 0) + 1
报ValueError: invalid literal输入里有空字符串或非数字改用无参split()
输出次数正确但组内乱序键函数漏了数值项补上kv[0]
输出末尾多空格用了循环print(end=' ')改用join
大数测试报错用了桶计数但数值超范围换回字典方案
只有部分用例通过没处理负数或空输入补边界用例验证

这张表可以贴在显示器边上,调试的时候一行行对,比盲目打断点快。我用它帮不少人定位过问题,平均下来一个问题不超过两分钟就能找到原因。

6. 从这道题往外延伸:计数思想还能怎么用

把这道题做对只是及格线,真正有价值的是把“计数加排序”这个模型抽象出来,套到别的题上去。省赛真题里这类变体非常多,换汤不换药,骨架永远是先聚合再排序。我梳理了三种最常见的延伸方向,每一种都附上改动点,你练熟之后遇到同类题基本不用重新思考。

6.1 计数排序与桶排序的关系

很多人把这道题和“计数排序”混为一谈,其实两者是不同层面的东西。计数排序是一种排序算法,它通过统计每个元素出现的次数,直接算出每个元素在有序结果中的位置,时间复杂度 O(n + R),但要求数据范围 R 不能太大。而这道题是“按频次排序”,排序的对象是不同元素的频次,本质上还是对键值对排序。

两者的联系在于都用到了“计数”这个动作。区别在于计数之后干什么:计数排序是拿次数做前缀和定位,本题是拿次数当排序键。我在理解这一层之后,看很多题就通透了——凡是题目里出现“出现次数”“频率”“重复了几次”,第一反应就是建频次表,然后再看是要按频次排、按频次筛选,还是按频次计算别的量。

举个延伸例子:如果题目改成“找出出现次数最多的那个数字,如果并列输出最小的”,那就不需要全排序了,一次遍历加上比较就能解决,复杂度降到 O(n)。虽然本题要求全部排序,但知道有更快的特例解法,说明你对问题结构有更深的理解。

6.2 同类变式题的改造方法

最常见的变式是换排序方向。比如题目改成“按次数从多到少,次数相同按数字从大到小”,改动点只有键函数里的第二个元素加负号:key=lambda kv: (-kv[1], -kv[0])。再比如“按次数从小到大,相同按数值从小到大”,那就是key=lambda kv: (kv[1], kv[0]),去掉负号即可。这四种组合我都建议写一遍跑一遍,形成条件反射,考场上就不用现推了。

第二种变式是加过滤条件,比如只输出出现次数大于 1 的数字。改动点是在排序前加一层筛选:ordered = [kv for kv in cnt.items() if kv[1] > 1]。这个筛选写在计数之后、排序之前最自然,也可以写在排序之后遍历输出时判断,但前者能让排序规模更小,性能更好。

第三种变式是换统计对象,比如从数字换成字符串、单词。这时候计数部分完全不用改,因为字典的键可以是任意可哈希对象,字符串天然支持。唯一要改的是int()转换那一步和输出时的类型转换,把str(k)改成直接k就行。我在练习时把这道题的数字换成一串单词跑过,逻辑一行都不用动,这也说明了抽象的价值——抓住“频次统计”这个本质,表层的数据类型只是皮。

第四种变式是要求输出前 k 个高频元素。这时候可以考虑用堆来做部分排序,把复杂度从 O(k log k) 降到 O(n log k),但本题这种规模直接用sorted切片[:k]完全够用,没必要上堆。我更倾向于先用简单方案,除非数据量明确很大再考虑优化,过早优化是浪费时间。

6.3 考场上的时间分配与调试节奏

最后说点非技术但很实用的东西。这道题在省赛里如果出现在前几道,我会给自己定一个十分钟的目标:读题两分钟,写核心逻辑五分钟,自测三分钟。超时不多就继续磨,超过十五分钟还没通过就先去拿后面的分,回头再回来调。

调试的顺序也要有讲究,不要一上来就打断点。我的习惯是先打印中间结果:把计数后的字典打印出来,看看频次对不对;再把排序后的列表打印出来,看看顺序对不对;最后看输出字符串的格式。三次打印基本就能定位问题在哪一段,比单步跟踪快得多。而且这个顺序是从上游到下游,符合数据流的方向,能避免在下游发现问题却在上上游找原因。

另外,我强烈建议在正式提交前把样例原样跑一遍,再把自测表里的七个用例跑一遍。样例只能证明你理解对了题意,自测用例才能证明代码健壮。我在早期比赛里因为省了这一步,在“全不同”用例上翻过车,那次教训之后,自测用例就成了我的固定动作,再赶时间也不省。

做这类频次统计的题,我个人最深的体会是:别急着写代码,先在纸上把计数结果和排序结果手算出来。手算一遍输入1 2 2 3 3 3 4 4的完整过程,你就知道键函数该怎么写、输出该怎么拼,写代码的时候几乎不会卡壳。手算花的那一分钟,往往能省下后面十分钟的调试。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询