重排数字得到2的幂：频次统计替代全排列（力扣869）

平时刷题最怕看到“重排”两个字，因为一旦老老实实把全排列拉出来，基本就离超时不远了。LeetCode 869 这道题正好踩在这个痛点上：题目是 Reordered Power of 2，中文叫“重新排序得到 2 的幂”，标题里还带着“耗时100”——我当时第一次见这题，确实折腾了很久，但想明白之后又觉得特别朴素。所以这篇就当是给自己留个复盘，也给卡在排列枚举里的朋友指条近路。

题目本身不难描述：给你一个正整数 n，可以任意重排它的数字，但新数字不能以 0 开头。请问是否存在某一种排列方式，使得得到的新数字恰好是 2 的某个整数次幂。比如 n = 1 返回 true，n = 10 返回 false；n = 46 时，46 不是 2 的幂，但重排成 64 之后是 2 的 6 次方，所以答案应该是 true。

这里不需要高深的数学，关键就是看你能不能从“穷举排列”的惯性思维里跳出来。我把完整推导、三种代码实现、以及我踩过的坑全部整理在下面，希望对你也有帮助。

1. LeetCode 869 先读懂题意：重排不是让你暴力枚举

1.1 一个容易被忽视的限定条件

题目里最容易被忽略的是两个词：正整数、不能以 0 开头。很多人一上来就把 n 转成字符串，然后itertools.permutations一把梭，想着 10 位以内也就几百万种排列，现代机器扛得住。

先别急着否定这种思路，我们认真算一下。n 最大是 10^9，也就是 10 个数字位。如果这 10 个数字互不相同，全排列数量是 10! = 3,628,800。三百六十万次排列，每次再判断一下是不是 2 的幂，在 C++ 里确实勉强能过，但 Python 直接跑全排列加上字符串拼接、整数转换，在线判题通常不会只跑一个用例，多来几个就非常紧张。

更关键的是：题目说的是“重排”，不是“排列”。有重复数字时，permutations会产生大量重复结果，你还得去重；没有重复数字时，3.6M 的上限又卡在那。这种解法写起来很爽，跑起来却很慌，属于典型的“能做但没必要”。

1.2 为什么全排列思路会在第 10 位数字前崩掉

很多人没有意识到，排列数量是随数字位数阶乘增长的，而阶乘是增长最恐怖的东西。n 是 10 位时约 360 万，听着还行；n 一旦超过 10 位，比如 12 位，那就是 4.79 亿，直接爆掉。本题虽然把 n 限制在 10 位以内，但 LeetCode 考察的从来不是“能不能暴力过这一题”，而是“能不能提炼出可复用的算法思想”。

如果每次输入都重新生成所有排列，时间复杂度就是 O(d!·d)，d 是位数。即使不考虑重复元素，d=10 也已经接近判题系统的极限；如果要应对多个测试点，内存和时间的抖动会非常明显。

所以我当时给自己定了一个原则：看到“重排”“排列”这类字眼，先别急着枚举，优先想两个问题。

• 目标集合是不是有限且很小？
• 能不能通过某种“特征”而不是“具体排列”来描述一个数？

这两个问题想清楚了，这题基本就解了一半。

2. 关键思路：排列等价于“字符频次一致”

2.1 频次统计为何天然规避前导零

两个数字能通过重排互相转换，本质上是它们拥有完全相同的数字组成，也就是每个数字 0-9 出现的次数完全一致。这一点很多人都能想到，但真正妙的地方在于：我们根本不需要关心“前导零”这个限制。

为什么？因为 2 的幂本身不可能以 0 开头。当我们在做频次匹配时，如果 n 的某个排列存在前导零，那个排列产生的数字根本不可能等于任何一个 2 的幂，所以它自然不会被匹配中。我们只需要检查“n 的整体频次”和“某个 2 的幂的整体频次”是否相等，前导零问题就自动消失了。

举个例子：n = 10，频次是 0 出现 1 次、1 出现 1 次。我们枚举 2 的幂：1、2、4、8、16、32、64、128……其中 16 的频次是 1 出现 1 次、6 出现 1 次，和 10 的频次不一致。没有任何一个 2 的幂的频次恰好是“一个 1 和一个 0”，因为 2 的幂里没有以 0 为有效数字开头的数，更不会有一位是 0、一位是 1 的正整数幂。所以直接返回 false，完全不用去处理“01”这种非法排列。

这就是频次统计最优雅的地方：把排列带来的顺序信息全部丢弃，只保留组成信息，反而避开了所有顺序相关的坑。

2.2 2 的幂的候选池到底有多少个

题目给出 n 最大是 10^9，也就是 10 位数字。那么 2 的幂中，同样不超过 10 位的有多少？我们来枚举一下：

2^0 = 1，2^1 = 2，2^2 = 4……一直到 2^29 = 536,870,912，这是 9 位数；2^30 = 1,073,741,824，正好是 10 位数，刚刚超过 10^9，但它的位数不超过 10，所以严格来说也可以进入候选池。题目没说 n 一定小于 2^30，只说了最大是 10^9。为了避免位数边界出问题，稳妥的做法是枚举到 2^30，或者直接枚举 31 个候选。

31 个候选是什么概念？这意味着我们只需要做最多 31 次频次对比。每次对比需要统计一个 2 的幂的各位数字，最多统计 10 位。所以总操作量是 31 × 10 = 310 这个量级，连“复杂”两个字都算不上。

这也给了一个通用启发：凡是“某个数重排后是否属于某个集合”的问题，只要这个集合里的元素个数很少，就可以用“特征匹配”代替“排列搜索”。2 的幂是典型的小集合，质数就不是，后面我会专门展开。

3. 直接可用的三套代码实现

3.1 Python 频次数组版

先给出一版最直观的写法，用长度为 10 的数组记录每个数字出现的次数。

class Solution: def reorderedPowerOf2(self, n: int) -> bool: # 统计 n 中每个数字 0-9 的出现次数 target = [0] * 10 tmp = n while tmp > 0: target[tmp % 10] += 1 tmp //= 10 # 枚举所有不超过 10 位的 2 的幂 power = 1 for _ in range(31): cur = [0] * 10 t = power while t > 0: cur[t % 10] += 1 t //= 10 # 如果频次完全一致，说明可以重排得到 if cur == target: return True power <<= 1 return False

这里有个细节：power <<= 1等价于乘以 2，而且比power *= 2更直观地表达了“2 的幂”这件事。while 循环统计数字频次时，要注意n本身不能为 0，因为题目限定正整数，所以可以放心用while tmp > 0而不是>=，不会漏掉任何情况。

3.2 Python 排序字符串版

如果不想写频次数组，Python 还有更短的等价解法：把数字转成字符串，排序后直接比较。因为“排序后的字符串相等”和“字符频次相等”是完全等价的。

class Solution: def reorderedPowerOf2(self, n: int) -> bool: target = ''.join(sorted(str(n))) for i in range(31): if ''.join(sorted(str(1 << i))) == target: return True return False

这个版本只有 6 行，胜在简洁。但要注意，str(1 << i)每次都会生成一个字符串，排序也要付出 O(L log L) 的开销。L 最多 10，影响不大，所以这种写法在 LeetCode 上完全够用。

不过我个人更推荐频次数组版，因为它的比较是 O(10) 的，而且不依赖字符串排序的底层实现，逻辑更可控。

3.3 C++ 参考实现

如果你习惯用 C++，也不复杂。用字符串作为频次表是很多解法里的常见操作，因为 C++ 的字符串可以当数组用。

class Solution { public: bool reorderedPowerOf2(int n) { string target = countDigits(n); for (int i = 0; i < 31; i++) { if (countDigits(1 << i) == target) { return true; } } return false; } private: string countDigits(int x) { string cnt(10, '0'); while (x > 0) { ++cnt[x % 10]; x /= 10; } return cnt; } };

这里把频次表直接编码成一个长度为 10 的字符串，因为每个字符只需要存 0-9 的出现次数，而 char 完全可以存下。这么做的好处是==可以直接比较整个字符串，代码看起来非常干净。

需要注意的是，string cnt(10, '0')初始化后，每个字符都是字符'0'，也就是 ASCII 码 48。执行++cnt[x % 10]会让对应的字符 ASCII 码递增，最后得到的就是频次信息。这是 C++ 里一个很实用的小技巧，但如果你不太习惯，也可以换成vector<int> cnt(10)，更直白。

3.4 边界条件自查表

写完代码后，我习惯做一张非常具体的边界自查表，一次性验证上面的实现不会翻车。

前导零最容易出错的其实是 10、100 这种结尾带零的数。你要是用生成排列再检查首位的方式，会多出很多无效递归；用频次匹配，这些情况全部走统一逻辑，省心很多。

4. 复杂度推导和“耗时100”的真相

4.1 时间与空间复杂度

先说结论：频次数组版的时间复杂度是 O(31 × 10) = O(1)，因为 2 的幂候选数量固定为 31，数字位数最多为 10。更形式化地说，如果 n 的位数为 L，2 的幂的候选数量是 O(L) 量级，因为 2 的幂按指数增长，位数每增加一，候选数量就多一个左右。总复杂度是 O(L^2)？这里要注意，我前面说候选数量约等于位数级别，所以是 O(L × L) = O(L^2)。但因为有上限（L ≤ 10），所以实际可以看成常数。

用排序字符串法的话，每次排序是 O(L log L)，总复杂度 O(31 × L log L)，依旧非常小。C++ 版本的字符串频次表每次只统计 10 位，和 Python 频次数组一致。

空间复杂度更简单：要么是长度为 10 的数组，要么是长度为 10 的字符串，全部是 O(1)。

4.2 常系数背后藏着哪些优化细节

标题里的“耗时100”，我当时看到有两种理解：一种是这题折腾了我大概 100 分钟才完全搞明白，另一种是最终解法耗时在 100 微秒以下。两种理解放在一起，其实并不矛盾，因为这题最大的成本不在运行，在思路转换。

但如果真要抠性能，有几个细节值得注意。

第一，枚举到 31 还是 30。2^30 = 1,073,741,824 是 10 位数，n 最大 10^9 也是 10 位。如果 n 输入 1,000,000,000，你只枚举到 2^29 也不会出问题，因为 2^30 的频次是 1、0、7、3、7、4、1、8、2、4 各若干次，和 1,000,000,000 的频次不同。但如果你觉得自己手动推边界不放心，直接写 31 次循环最保险。题目如果哪天改了限制，多一次枚举也不会错。

第二，提前算好 n 的位数可以剪枝吗？可以，但对这题帮助不大。比如 n 是 3 位数，那你根本不关心所有不是 3 位数的 2 的幂。确实可以跳过一些无谓统计，但最多也就跳过大约 30 次里的几次，没必要为了这个优化牺牲代码可读性。

第三，重复统计 2 的幂的频次。如果你要在同一个进程里跑很多个测试用例，可以把所有 2 的幂的频次预计算好，放到全局变量里。LeetCode 调用同一个 Solution 对象多次时，全局缓存能省掉大量重复工作。

# 全局变量缓存所有 2 的幂的频次 _power_freq = None def _build_cache(): global _power_freq if _power_freq is None: _power_freq = [] for i in range(31): power = 1 << i freq = [0] * 10 while power: freq[power % 10] += 1 power //= 10 _power_freq.append(freq)

这样每次调用只需要统计 n 的频次，再和缓存里的最多 31 个频次逐一比较。LeetCode 判题时单个用例的时间可以压到非常低，实测下来非常稳。

5. 新手最容易踩的四个坑

5.1 直接用 n & (n - 1) 判断导致漏判

这是我最常见到的错误。很多人看到“2 的幂”三个字，第一反应就是n & (n - 1) == 0，于是直接对原始 n 做位运算判断。

这个思路错得很隐蔽。题目允许重排，所以即使 n 本身不是 2 的幂，它的排列可能是。比如 n = 61，61 & 60显然不是 0，但你把它倒过来就是 16，16 是 2 的幂，答案应该是 true。直接用位运算判断原始 n，直接把 61 这种用例毙掉了。

正确的检查对象应该是“某个排列”，而不是“原始整数”。这也是为什么所有可行解法都绕不开频次或者排序的原因：你必须把 n 打散，而不是把它当作一个整体来判断。

5.2 把“包含”当成“重排”

还有一部分人写出来的逻辑是：遍历 2 的幂，看它的数字是否都出现在 n 里，或者说 n 的每个数字是否都在某个 2 的幂里出现。这种思路混淆了两个概念。

重排要求的是每个数字出现的次数完全相等，而不是子集关系。n = 112，包含两个 1 和一个 2，这时候 2 的幂 128 里也有 1 和 2，但还有一个 8，数量关系对不上。如果只关注“包含”，就会错判 112 可以重排成 128，实际上位数都不一样。

判断“可以用某一组字符重新排列成另一个字符串”的充要条件是：长度相同，且每个字符出现次数完全相同。少一个条件都不行。

5.3 前导零过滤处理过度

有些人确实想到了前导零问题，于是会在生成排列时跳过首位为 0 的情况，这本身没错。但问题在于，很多初学者用递归生成排列时，为了过滤前导零写了大量额外判断，比如判断首位是否为零、判断当前排列是否合法、判断是否已经使用过相同数字，结果代码越写越复杂，错误率直线上升。

频次匹配的巧妙之处是不需要任何前导零过滤。因为当你比较 n 的频次和某个 2 的幂的频次时，那个 2 的幂本身没有前导零。你可以想成：如果 n 有一个合法排列等于这个 2 的幂，那这个合法排列的首位自然是 2 的幂的首位，不可能是 0。所以前导零的约束已经隐含在“和 2 的幂相等”里了。

如果你发现自己为了前导零写了很多显式过滤逻辑，大概率是走回了枚举排列的老路。

5.4 for 循环只枚举到 30 还是 31

还有一个很不起眼但容易卡人的边界：2 的幂要枚举到多少。我见过有人写成for i in range(30)，理由是 2^30 大于 10^9。这其实犯了一个边界理解错误：题目限定了 n 不超过 10^9，但 n 的位数是 10，而 2^30 = 1073741824 恰好是 10 位数。如果 n = 1000000000，虽然它本身大于所有小于它的 2 的幂，但它的位数和 2^30 相同，必须参与比较才能保证逻辑完备。

当然，由于频次不同，不参与也不会导致错误答案，但从“枚举全部候选”的角度，循环 31 次更符合定义。2 的 0 次方到 2 的 30 次方，一共 31 个候选，一个不多一个不少。

6. 换一个问题：重排成质数或者找出具体排列

6.1 重排成质数还能用同一套思路吗

刷完这题，很容易想到一个变种：给定正整数 n，重排它的数字，问能不能得到一个质数。

这个问题的答案就没那么理想了。2 的幂在 10^9 以内只有 31 个，质数却有五千多万个。你不可能把所有质数的频次都预计算好，再和 n 的频次比较。因为你不仅要存五千多万个频次，还要考虑内存，明显不现实。

所以“频次匹配”这套思路，只在目标集合足够小的时候才高效。如果目标是质数，更适合的方向是回溯 + 剪枝：先生成所有不重样、不以 0 开头的排列，然后对每个排列做质数判断，同时利用数位和、末尾奇偶等条件剪枝。

这其实也反过来提醒我们：LeetCode 869 能这么做，本质上是沾了“2 的幂”指数增长、候选极少的便宜。这不是套路万能，而是正确识别了目标集合的规模。

6.2 如果题目要求输出具体排列

面试时可能会被追问：如果不仅返回 true/false，而是要把具体哪一组排列返回，怎么办？

这时候就不能只做频次匹配了，因为频次匹配只告诉我们“存在”，但不告诉我们“怎么排列”。你需要回到回溯算法，建立一个长度为 L 的数组，每个位置依次尝试放 0-9 中剩余的数字，并跳过前导零的情况。完成一个完整排列后，再判断它是不是 2 的幂。

此时可以用一个小优化：没有必要生成所有排列再逐一判断。可以先枚举所有 2 的幂，然后检查当前 2 的幂是否可以通过重排 n 得到，如果能就直接返回它的字符串形式。换句话说，把“找排列”转化成“找幂”，也是一种很好的反向思维。我在实际给朋友讲这道题时，就推荐用这个思路去处理追问，代码量比纯回溯更少，逻辑也更顺。

6.3 如果 n 变得特别大怎么办

LeetCode 原题的 n 限制在 10^9 以内，所以 31 个候选很轻松。但如果 n 是一个 100 位的大整数，比如面试官突然把数据范围拉大，这道题还能用频次匹配吗？

仍然可以，但要注意两点。第一，2 的幂的候选数量会随着位数线性增长，100 位大约对应 333 个候选，依然不多。第二，每次统计频次需要遍历 100 位，总复杂度大约是 333 × 100，也就是三万多次操作，依然完全可以接受。

所以从更广的视角看，这题的复杂度本质是 O(L²)，其中 L 是数字位数。L=10 时是 100，L=100 时是一万，增长可接受，远好于阶乘级别的排列枚举。这也是为什么“频次统计 + 小候选集”这个组合在数据处理里很常用。

7. 个人刷题体会

最后说点题外话。我当时拿到这题，第一版代码用的就是生成排列，本地跑了几组数据都通过，自我感觉良好。结果提交之后，虽然勉强过了，但时间和内存排名都很难看。后来静下心分析，才发现全排列完全绕了远路，真正该做的事情不过是把“顺序”这个无关信息丢掉。

这件事让我有两点很深的感触。

第一，看到“重排”“排列组合”不要条件反射式地递归。先想想问题的逆命题：既然目标是 2 的幂，那 2 的幂到底有多少个？如果目标集合小到可以枚举，那大概率可以用“频次特征”去匹配，而不是去生成所有排列。反过来，如果目标集合很大，再回去考虑回溯剪枝也不迟。

第二，边界条件要建立成表格，而不是靠脑子想。我后来每次刷题都会把特殊输入写成一个表，逐行验证。LeetCode 869 里的 10、46、100 这类用例，几乎覆盖了前导零、非平凡重排、多位数匹配三个主要风险点，自查一次能省下很多调试时间。

如果你也卡在这道题上，我建议你按这个顺序试：先不看题解，自己算一下 2 的幂在数据范围内有多少个；想明白这一点，解题思路基本就自己浮出来了。剩下的代码，反而只占整个思考过程的一小部分。