江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第357题：计算各个位数不同的数字个数

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^n。

📖 文章摘要

本文详细解析LeetCode第357题“计算各个位数不同的数字个数”，这是一道数学问题。文章提供了基于排列组合的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数学思维和组合问题的读者。

核心知识点： 排列组合、数学分析、动态规划 难度等级： 中等 推荐人群： 具有一定数学基础，想要提升组合问题解决能力的程序员

题目描述

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^n。

示例

示例 1：

输入：n = 2
输出：91
解释：答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

示例 2：

输入：n = 0
输出：1

提示

  • 0 <= n <= 8

解题思路

本题可以使用排列组合的方法解决：

  1. 对于n位数，第一位有9种选择（1-9）
  2. 第二位有9种选择（0-9除去第一位）
  3. 第三位有8种选择（0-9除去前两位）
  4. 以此类推…

时间复杂度： O(n) 空间复杂度： O(1)

图解思路

位数分析表

位数 选择数 说明
1 9 1-9
2 9 0-9除去第一位
3 8 0-9除去前两位
4 7 0-9除去前三位

计算过程表

n 计算过程 结果
0 1 1
1 9 10
2 9 * 9 91
3 9 * 9 * 8 739

代码实现

C# 实现

public class Solution {
    public int CountNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        
        int result = 10;
        int available = 9;
        int current = 9;
        
        for (int i = 2; i <= n; i++) {
            current *= available;
            result += current;
            available--;
        }
        
        return result;
    }
}

Python 实现

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        if n == 1:
            return 10
            
        result = 10
        available = 9
        current = 9
        
        for i in range(2, n + 1):
            current *= available
            result += current
            available -= 1
            
        return result

C++ 实现

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        
        int result = 10;
        int available = 9;
        int current = 9;
        
        for (int i = 2; i <= n; i++) {
            current *= available;
            result += current;
            available--;
        }
        
        return result;
    }
};

执行结果

C# 实现

  • 执行用时：0 ms
  • 内存消耗：5.2 MB

Python 实现

  • 执行用时：32 ms
  • 内存消耗：13.2 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：5.8 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 0 ms 5.8 MB 执行效率最高
C# 0 ms 5.2 MB 内存占用最小
Python 32 ms 13.2 MB 代码简洁，易于理解

代码亮点

  1. 🎯 使用排列组合公式高效计算
  2. 💡 处理边界情况（n=0和n=1）
  3. 🔍 优化计算过程，避免重复计算
  4. 🎨 代码结构清晰，易于维护

常见错误分析

  1. 🚫 未考虑n=0的特殊情况
  2. 🚫 计算过程中整数溢出
  3. 🚫 重复计算导致效率低下
  4. 🚫 未处理n>8的情况

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
排列组合 O(n) O(1) 高效，实现简单 需要数学知识
暴力枚举 O(10^n) O(1) 直观，易于理解 效率极低

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第357题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！