2026-06-19：阶数数字排列。用go语言，给定一个整数 n，判断能否把 n 的各位数字重新排列（允许使用原来的顺序，也允许换成任意顺序），

福大大架构师每日一题

发布于 2026-06-24 15:51:48

1120

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-06-19：阶数数字排列。用go语言，给定一个整数 n，判断能否把 n 的各位数字重新排列（允许使用原来的顺序，也允许换成任意顺序），得到某个有效整数，使得它满足下面的性质：

• 对这个新整数的每一位数字 d，计算 d!（d 的阶乘）。
• 把所有位数字的阶乘结果相加。
• 如果这个“位数字阶乘之和”恰好等于该整数本身，则这个整数称为“阶数数字”。

要求考虑所有排列的可能性，但排列必须是有效的：不能以 0 开头（否则该排列视为无效）。

如果存在至少一种有效排列能形成阶数数字，返回 true；否则返回 false。

1 <= n <= 1000000000。

输入： n = 145。

输出： true。

解释：

数字 145 本身是一个阶数数字，因为 1! + 4! + 5! = 1 + 24 + 120 = 145。因此，答案为 true。

题目来自力扣3848。

一、整体解题核心思路先梳理

题目要求：给定数字n，把它所有数字做不含前导0的排列，只要任意一个排列x满足「x每一位阶乘相加 = x本身」，就返回true。核心数学关键点：

1. 不管数字怎么排列，各位数字集合不变 → 各位数字阶乘的总和S是固定值，和排列顺序无关；
2. 假设某排列x是合法阶数数字，则必然满足 x = S；
3. 推论：唯一有可能符合条件的候选数字，只能是各位阶乘总和S。只需要验证两件事： ① S的数字多重集合和原数字n的数字多重集合完全相同（即互为排列）； ② S不能以0开头（S自身自然不会前导0，因为是正常整数）。原代码完全基于这个推论实现，不需要枚举所有排列，极大降低复杂度。

二、分步骤详细拆解执行流程（以输入n=145举例）

步骤1：全局预处理0~9的阶乘数组（init函数预计算，程序启动只执行一次）

1. 定义长度为10的数组fac，初始fac[0]=1（数学规定0! = 1）；
2. 循环i从1到9，依次计算每个数字的阶乘：
- • fac[1] = fac[0] * 1 = 1! = 1
- • fac[2] = fac[1] * 2 = 2! = 2
- • fac[3] = 6、fac[4]=24、fac[5]=120……直到fac[9]=362880；
3. 作用：后续取数字d时，直接查表拿d!，不用重复计算阶乘。

步骤2：进入判断函数 isDigitorialPermutation(n int)，分三大阶段

阶段A：遍历原数字n的每一位，完成两件事：累加阶乘和、统计数字出现次数

输入示例n=145，循环条件 n>0，每次对10取模取个位，再除以10截断：

1. 初始化两个变量：
- • sumFac：存储所有位阶乘累加和，初始0；
- • cnt[10]数组：长度10，记录0-9每个数字在原数里出现的次数，初始全0；
2. 第一轮 n=145： d = 145 % 10 = 5；sumFac += fac[5]=120 → sumFac=120；cnt[5] +=1 → cnt[5]=1；n更新为14；
3. 第二轮 n=14： d=14%10=4；sumFac += fac[4]=24 → sumFac=144；cnt[4] +=1 → cnt[4]=1；n更新为1；
4. 第三轮 n=1： d=1%10=1；sumFac += fac[1]=1 → sumFac=145；cnt[1] +=1 → cnt[1]=1；n更新为0；
5. 循环终止；此时得到：

• sumFac = 145（所有数字阶乘总和）；
• cnt数组记录原数字：1出现1次、4出现1次、5出现1次，其余数字0次。

阶段B：遍历候选数字sumFac的每一位，抵消cnt数组计数

核心逻辑：如果sumFac和原数n是数字重排列，那么两者每个数字出现次数完全相等，遍历sumFac每一位，对应cnt数字计数减1，最终所有cnt必须归零。循环条件 sumFac>0，每次取个位、除以10：

1. 第一轮 sumFac=145：个位5 → cnt[5] -=1 → cnt[5]=0；sumFac=14；
2. 第二轮 sumFac=14：个位4 → cnt[4] -=1 → cnt[4]=0；sumFac=1；
3. 第三轮 sumFac=1：个位1 → cnt[1] -=1 → cnt[1]=0；sumFac=0；
4. 循环终止；

阶段C：校验cnt数组是否全部为0，返回布尔结果

1. 对比cnt数组和全零数组[10]int{0,0,...0}；
2. 示例中所有位置都是0，等式成立，返回true；补充反例：若原数是146，sumFac=1!+4!+6! = 1+24+720=745；遍历745会给cnt[7]、cnt[4]、cnt[5]减1，原cnt是1、4、6各一次，最终数组存在非0数字，返回false。

步骤3：main函数执行流程

1. 给定输入n=145；
2. 调用判断函数，接收返回布尔值；
3. 打印输出结果true。

三、补充边界逻辑说明（题目限制n∈[1,1e9]）

1. 前导0校验：本算法天然规避无效排列问题。若存在合法无0开头排列x满足条件，则x=sumFac，sumFac是普通正整数，本身不可能以0开头；若sumFac首位为0，只能是sumFac=0，但n≥1，原数字至少有1个非0数字，sumFac不可能为0，无需额外判断前导0；
2. 无需枚举全排列：常规暴力枚举数字排列会产生阶乘级复杂度，本算法利用「排列数字阶乘和固定」的数学性质，只校验唯一候选sumFac，完全跳过排列枚举。

四、时间复杂度分析

1. 预处理阶乘（init）

固定循环0~9，循环次数恒定10次 → O(1) 常数时间，只执行一次。

2. isDigitorialPermutation 内部两段数字遍历

设输入数字n的位数为k（题目上限1e9，最多10位）：

• 遍历原数字n：最多10次循环 O(k)=O(1)；
• 遍历sumFac：单个数字阶乘最大9!=362880，10位数字总和上限 10*362880=3,628,800，最多7位数字，循环次数最多7次 O(1)；
• 数组相等对比：固定长度10的数组逐元素比较，10次操作 O(1)；

整体单次判断函数时间：O(1)，与输入数值大小无关。全局总时间复杂度：O(1)（常数级）。

五、额外空间复杂度分析

额外开辟的存储空间：

1. 全局fac数组：固定长度10，O(1)；
2. 函数内cnt数组：固定长度10，O(1)；
3. 局部变量sumFac、d、循环计数器：单个int变量，常数空间；

不存在随输入长度增长的动态数组、切片、递归栈等。总额外空间复杂度：O(1)（常数空间）。

Go完整代码如下：

package main

import (
    "fmt"
)

var fac = [10]int{1}

func init() {
    // 预处理阶乘
    for i := 1; i < len(fac); i++ {
        fac[i] = fac[i-1] * i
    }
}

func isDigitorialPermutation(n int)bool {
    sumFac := 0
    cnt := [10]int{}
    for ; n > 0; n /= 10 {
        d := n % 10
        sumFac += fac[d]
        cnt[d]++
    }

    for ; sumFac > 0; sumFac /= 10 {
        cnt[sumFac%10]--
    }

    // cnt[i] == 0
    return cnt == [10]int{}
}

func main() {
    n := 145
    result := isDigitorialPermutation(n)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

# 预处理阶乘
fac = [1] * 10
for i in range(1, len(fac)):
    fac[i] = fac[i-1] * i

def is_digitorial_permutation(n: int) -> bool:
    sum_fac = 0
    cnt = [0] * 10
    
    # 计算各位数字阶乘之和，并统计各位数字出现次数
    temp = n
    while temp > 0:
        d = temp % 10
        sum_fac += fac[d]
        cnt[d] += 1
        temp //= 10
    
    # 对阶乘和的各位数字，减少对应计数
    while sum_fac > 0:
        cnt[sum_fac % 10] -= 1
        sum_fac //= 10
    
    # 检查所有计数是否为 0
    return all(c == 0for c in cnt)

def main():
    n = 145
    result = is_digitorial_permutation(n)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <array>
using namespace std;

// 预处理阶乘
array<int, 10> fac;

void initFac() {
    fac[0] = 1;
    for (int i = 1; i < 10; i++) {
        fac[i] = fac[i-1] * i;
    }
}

bool isDigitorialPermutation(int n) {
    int sumFac = 0;
    array<int, 10> cnt = {0};

    // 计算各位数字阶乘之和，并统计各位数字出现次数
    int temp = n;
    while (temp > 0) {
        int d = temp % 10;
        sumFac += fac[d];
        cnt[d]++;
        temp /= 10;
    }

    // 对阶乘和的各位数字，减少对应计数
    while (sumFac > 0) {
        cnt[sumFac % 10]--;
        sumFac /= 10;
    }

    // 检查所有计数是否为 0
    for (int i = 0; i < 10; i++) {
        if (cnt[i] != 0) {
            returnfalse;
        }
    }
    returntrue;
}

int main() {
    initFac();

    int n = 145;
    bool result = isDigitorialPermutation(n);
    cout << (result ? "true" : "false") << endl;

    return0;
}