错误代码按频率排序

题目

给一个整数数组，每个数代表一个错误代码。要求按「重要程度」把整个数组重新排列后返回，规则是：

• 出现次数（也就是频率，frequency）越少的代码越重要，排在越前面；
• 出现次数相同时，数值越小的排在越前面；
• 返回重排后的完整数组，重复的代码全部保留，所以同一个代码的几个副本会连成一段。

原帖没给函数签名、输入格式和数据范围，也没给样例。下文说的「站方 AI」，指一亩三分地在帖子页上用 AI 自动整理出来的内容，这类内容可能编造细节，只能当线索。

样例（站方 AI 整理，未经原帖证实；按原帖的两条规则手算，结果是一致的）：[4, 5, 6, 5, 4, 3] → [3, 6, 4, 4, 5, 5]。3 和 6 各出现 1 次，3 更小，排在前面；4 和 5 各出现 2 次，4 更小，排在前面。站方 AI 还写了数据范围：数组长度 n 满足 1 ≤ n ≤ 2×10^5，值域 -10^9～10^9（站方 AI 整理，未经原帖证实）。

还有一篇面经的描述要模糊得多，只说先数出频率，再按频率排好序返回列表。它没说频率高的在前还是低的在前，没说频率相同时怎么排，也没说返回的是去重后的值，还是每个值按出现次数重复输出的完整数组。站方 AI 把这篇补成了「频率从高到低、按次数展开、同频任意」，这些都不是原帖说的。【推断】这篇考的和上面是同一道题：它和上面那篇都是同一时期的实习 OA，而且另一道编程题都是把相邻位置的下降量（前一项比后一项大出来的部分）累加起来的那道，只是这篇对本题描述得很简略。

这道题和 LeetCode 1636（Sort Array by Increasing Frequency）几乎一样，唯一的差别在频率相同时的顺序：1636 是数值大的在前，这里是数值小的在前。

面经里怎么考的

2026-03 下旬，2026 年夏季 SDE 实习（应届硕士）的 OA 里出了这道题，是两道编程题里的第一题。第二题是 子数组加值变非递减：每次可以给一段连续区间整体加上一个正数，要让数组变成非递减，并且加上的总量最小，答案是所有相邻下降量之和。帖子里没写限时多久，也没写用的是哪个考试平台。

• 一位发帖人用 collections.Counter 计数，排序时把 sort 的 key 参数设成（频率，数值）这个元组（tuple）。发帖人没说通过了几个测试用例（test case），帖子标注的结果是 Pass。
• 另一位发帖人拿到 OA 当天就做完了，5 天后收到一封「下一轮怎么准备」的邮件，可以认为 OA 过了。这位发帖人觉得两道题比自己看过的大多数面经里的题都简单，用 dict 计数、再用 lambda 写排序键（sort key）就能做出来。编程题之后还有 Work Simulation 和性格测试（Amazon 的叫法是 Work Style）。Work Simulation（情景判断题）是 Amazon OA 里给你一个日常工作场景、让你给几种处理方式打分或排序的部分，这位发帖人遇到的题里有和邮件相关的。这两部分详见 Work Simulation 与 Work Style。

这道题本身没有难度，能丢分的地方只有一种，就是把规则读反。容易读反的有三处：频率是升序还是降序，频率相同时按数值升序还是降序，返回的是展开后的完整数组还是去重后的代码。所以考试时要逐字读完题面再写排序键，写完拿题面给的样例手动过一遍。

上面这些都是实习岗的 OA；AWS SDE II 的 OA 会不会从同一个题库出题，未核实。

思路

下面先讲主解（下文都这么叫，对应代码里的 sort_error_codes）：用哈希表（hash table）数出每个代码出现的次数，再对原数组排序，排序键用（次数，数值）这个元组。Python 的元组按字典序（lexicographical order）比较，也就是先比第一项次数，次数相同再比第二项数值，正好对应题目的两条优先级。因为数值也在键里，同一个代码的所有副本键完全相同，而不同代码的键一定不同，所以排完之后同一个代码的副本自然连成一段。

还有一种分组写法，也就是代码里的 sort_error_codes_grouped：只对 m 个不同的代码排序，再把每个代码按出现次数重复输出。参与排序的元素从 n 个减少到 m 个，排序部分降到 O(m log m)。实际快多少要看数据。主解本机实测 n = 2×10^5 时约 0.1～0.3 秒，不同的值越多越慢。不同的值少时（m 远小于 n），分组写法要排的元素少得多，所以快得多：值域 0～1000 时分组写法约 0.01 秒，主解约 0.12 秒。反过来，所有值都不同时 m 等于 n，两种写法排序的工作量一样，分组写法还多了一步展开，所以略慢一点。两种写法在这个规模下都不到一秒，主解更短、更不容易写错，OA 里写主解就够了。

代码

下面的代码已运行。样例和边界用例见「测试用例」一节；那一节还用暴力解在随机小数据上对比了结果，这种做法叫对拍。

from collections import Counter


def sort_error_codes(codes):
    cnt = Counter(codes)
    return sorted(codes, key=lambda x: (cnt[x], x))


def sort_error_codes_grouped(codes):
    # 等价写法：只排不同的值，再按次数展开
    cnt = Counter(codes)
    res = []
    for x in sorted(cnt, key=lambda v: (cnt[v], v)):
        res.extend([x] * cnt[x])
    return res


if __name__ == "__main__":
    print(sort_error_codes([4, 5, 6, 5, 4, 3]))  # [3, 6, 4, 4, 5, 5]

如果函数签名要求原地修改（in-place）、不返回值，就先算好 cnt，再写 codes.sort(key=lambda x: (cnt[x], x))，结果和上面相同（已运行）。

复杂度

主解的时间复杂度是 O(n log n)，瓶颈在对 n 个元素排序，计数只要 O(n)。分组写法是 O(n + m log m)，其中 m 是不同代码的个数：计数和按次数展开各是 O(n)，排序只排 m 个代码。空间是 O(n)，其中计数表占 O(m)，再加上长度为 n 的输出数组。

易错点

• 如果排序键只写次数 key=lambda x: cnt[x]，频率相同的不同代码会保持原来的交错顺序。这是因为 Python 的排序是稳定的（stable），键相同的元素保持原有的相对顺序。比如 [5, 4, 5, 4] 排完还是 [5, 4, 5, 4]，正确答案是 [4, 4, 5, 5]。所以数值一定要放进键里。
• 做过 LeetCode 1636 的人容易顺手写成 (cnt[x], -x)，因为那道题频率相同时数值大的在前。这里正好相反，频率相同时数值小的在前，键是 (cnt[x], x)。
• 本题是频率低的在前，别把方向读反。如果考场上的题面是频率高的在前，键要改成 (-cnt[x], x)，对频率取负数之后，升序排序就变成了频率从高到低。
• 数据里可能有负数，但负数不需要特殊处理。「数值越小越靠前」比的是带正负号的大小，不是绝对值，所以直接用默认的整数比较就对了，频率相同时 -6 照样排在 4 前面（测试用例第二张表的最后一行就是这种情况）。
• 如果从输入读进来的是字符串，要先转成 int。字符串是按字符逐个比较的，不是按数值大小，所以不转的话 "10" 会排在 "9" 前面。
• 要返回的是展开后的完整数组（长度等于 n），不是去重后的代码列表。只有题面要求去重后的列表时，才用 sorted(cnt, key=...)。

测试用例

下面用同一组输入对比本题和 LeetCode 1636 的输出，两者只在频率相同时的先后方向上不同。第一行里三个值的频率各不相同，所以两边结果一样。

除了上面的固定用例，还用暴力解在随机小数据上和主解做了对拍。暴力解写了两个，彼此独立：第一个按频率 1、2、…、n 逐级枚举，每一级里把这个频率的不同值从小到大输出；第二个是插入排序，每次比较两个数时都现场调用 count 重新数出现次数。随机生成了 3000 组输入，长度 0～12，值域有只取 0～3 的、带负数的、只有一个值的几种。主解、分组写法和两个暴力解的输出全部一致。Follow-up 一节里写了代码的变体（频率降序、LeetCode 1636 的规则、只返回去重后的代码、只取前 k 个、频率相同按首次出现排）也各自和暴力解对拍过；最后一条用计数数组的做法没写代码，所以没有对拍。

Follow-up

• 如果频率高的在前（另一篇面经的说法有可能是这个意思），把键改成 (-cnt[x], x)（对频率取负数，道理见易错点），[4, 5, 6, 5, 4, 3] → [4, 4, 5, 5, 3, 6]。
• 如果频率相同时数值大的在前，这就是 LeetCode 1636，键改成 (cnt[x], -x)。
• 如果只返回去重后的代码，直接对计数表的键排序，写成 sorted(cnt, key=lambda v: (cnt[v], v))，[4, 5, 6, 5, 4, 3] → [3, 6, 4, 5]。
• 如果只要最重要的前 k 个代码，计数后用 heapq.nsmallest(k, cnt, key=lambda v: (cnt[v], v)) 取排序键最小的 k 个。它内部只维护一个大小为 k 的堆（heap），所以是 O(n + m log k)，k 小的时候比把 m 个代码全排一遍省。思路和 347. Top K Frequent Elements 一样。
• 如果频率相同时按首次出现的先后排，先扫一遍，记下每个代码第一次出现的下标 first[x]，再把键换成 (cnt[x], first[x])。[4, 5, 6, 5, 4, 3] → [6, 3, 4, 4, 5, 5]。
• 如果错误码的值域很小（比如 0～999），可以用计数数组代替哈希表：数组下标就是错误码，存的是出现次数。然后按频率分桶，也就是桶排序（bucket sort）的思路：按值从小到大扫一遍计数数组，把每个值放进对应频率的桶，这样桶内自然是按值升序的，最后按频率从低到高依次输出各个桶，桶里每个值按它的出现次数重复输出。总时间 O(n + 值域)，不需要比较排序（comparison sort）。

英文讲法

I count each error code with a hash map, then sort the original array using the key (frequency, value). Tuples compare lexicographically, so lower frequency comes first and ties go to the smaller code. Because the value is part of the key, all copies of the same code end up next to each other. That's O(n log n) time and O(n) space.

If they want the most frequent codes first, I negate the frequency in the key; if ties should go to the larger value, I negate the value instead, which is the LeetCode 1636 version.