Medium

题目描述

给定一个整数 n。

如果一个数字的各位数字的阶乘之和等于该数字本身，则称该数字为"数字阶乘数"。

判断 n 的任意排列（包括原始顺序）是否能形成数字阶乘数。

如果存在这样的排列，返回 true，否则返回 false。

注意：

  • 非负整数 x 的阶乘，记作 x!，是所有小于等于 x 的正整数的乘积，且 0! = 1。
  • 排列是指对数字的所有位数进行重新排列，且不能以零开头。任何以零开头的排列都是无效的。

示例 1：

输入：n = 145
输出：true
解释：数字 145 本身就是数字阶乘数，因为 1! + 4! + 5! = 1 + 24 + 120 = 145。因此答案是 true。

示例 2：

输入：n = 10
输出：false
解释：10 不是数字阶乘数，因为 1! + 0! = 2 不等于 10，而且排列 "01" 无效，因为它以零开头。

约束条件：

  • 1 <= n <= 10^9

提示：

  • 预计算数字 0 到 9 的阶乘，并计算各位数字阶乘的和。
  • 检查这个和的各位数字是否能使用 n 的各位数字恰好组成（不允许前导零）。

解题思路

这道题的核心思路是：判断 n 的任意排列是否能形成数字阶乘数。

解题步骤：

  1. 预计算阶乘：预先计算 0-9 每个数字的阶乘值，便于后续计算。

  2. 计算阶乘和：将 n 的每个数位提取出来，计算对应阶乘的和 sum。

  3. 检查数字匹配：判断 sum 的各个数位是否与 n 的各个数位完全相同（即是否为排列关系）。

  4. 处理前导零：如果 sum 包含前导零，需要特殊处理，确保存在有效的排列（不以零开头）。

关键观察：

  • 数字阶乘数是固定的，只有少数几个：1, 2, 145, 40585
  • 由于 n 的范围限制在 10^9，我们只需要考虑较小的数字阶乘数
  • 重点是检查两个数字是否为排列关系，即各数位的计数相同

算法优化： 可以通过字符计数或排序来快速判断两个数字是否为排列关系。

代码实现

class Solution {
public:
    bool isDigitorialPermutation(int n) {
        vector<int> factorial = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        
        // 计算 n 各位数字阶乘的和
        int sum = 0;
        int temp = n;
        while (temp > 0) {
            sum += factorial[temp % 10];
            temp /= 10;
        }
        
        // 检查 sum 和 n 是否为排列关系
        string s1 = to_string(n);
        string s2 = to_string(sum);
        
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        
        return s1 == s2;
    }
};

class Solution:
    def isDigitorialPermutation(self, n: int) -> bool:
        factorial = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
        
        # 计算 n 各位数字阶乘的和
        digit_sum = 0
        temp = n
        while temp > 0:
            digit_sum += factorial[temp % 10]
            temp //= 10
        
        # 检查 digit_sum 和 n 是否为排列关系
        s1 = sorted(str(n))
        s2 = sorted(str(digit_sum))
        
        return s1 == s2

public class Solution {
    public bool IsDigitorialPermutation(int n) {
        int[] factorial = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        
        // 计算 n 各位数字阶乘的和
        int sum = 0;
        int temp = n;
        while (temp > 0) {
            sum += factorial[temp % 10];
            temp /= 10;
        }
        
        // 检查 sum 和 n 是否为排列关系
        char[] s1 = n.ToString().ToCharArray();
        char[] s2 = sum.ToString().ToCharArray();
        
        Array.Sort(s1);
        Array.Sort(s2);
        
        return new string(s1) == new string(s2);
    }
}

var isDigitorialPermutation = function(n) {
    const factorials = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880];
    
    const digits = n.toString().split('').map(Number);
    const sum = digits.reduce((acc, digit) => acc + factorials[digit], 0);
    
    const sumDigits = sum.toString().split('').map(Number);
    
    if (digits.length !== sumDigits.length) return false;
    
    digits.sort();
    sumDigits.sort();
    
    for (let i = 0; i < digits.length; i++) {
        if (digits[i] !== sumDigits[i]) return false;
    }
    
    return sum > 0 && !sum.toString().startsWith('0');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(d log d)
空间复杂度O(d)

其中 d 是数字的位数。时间复杂度主要来自排序操作，空间复杂度主要用于存储字符串。