统计不重复数字的数字个数

1. 概述

本文探讨如何统计满足以下条件的数字个数：数字的所有位都不重复，且数字总位数不超过给定整数 n。我们将从暴力解法到优化方案逐步分析，并附上示例代码和复杂度分析。

2. 问题陈述

给定整数 n，统计所有满足条件的正整数 x：

0 <= x < 10^n（即 x 是小于 10^n 的正整数）
x 的每位数字均不重复

几个典型示例：

当 n=0 时，唯一满足条件的数字是 0
当 n=1 时，所有个位数都满足：0,1,2,3,4,5,6,7,8,9
当 n=2 时，包含所有个位数及部分两位数（如 10,12,13），但排除 11 这类重复数字
当 n=3 时，满足条件的数字如 0,1,2,3,12,13,23,345,745 等
当 n=4 时，新增如 1234,1567 等四位数

3. 解决方案

3.1. 暴力解法

最直观的思路是遍历所有小于 10^n 的数字，逐个检查数字是否包含重复位。虽然实现简单，但当 n 增大时效率会急剧下降。

核心步骤：

遍历 0 到 10^n - 1 的所有数字
对每个数字检查是否包含重复位
统计满足条件的数字个数

int bruteForce(int n) {
    int count = 0;
    int limit = (int) Math.pow(10, n);
        
    for (int num = 0; num < limit; num++) {
        if (hasUniqueDigits(num)) {
            count++;
        }
    }
    return count;
}

辅助方法 hasUniqueDigits 通过字符串转换检查重复位：

boolean hasUniqueDigits(int num) {
    String str = Integer.toString(num);
    for (int i = 0; i < str.length(); i++) {
        for (int j = i + 1; j < str.length(); j++) {
            if (str.charAt(i) == str.charAt(j)) {
                return false;
            }
        }
    }
    return true;
}

验证测试用例：

@Test
void givenNumber_whenUsingBruteForce_thenCountNumbersWithUniqueDigits() {
    assertEquals(91, UniqueDigitCounter.bruteForce(2));
}

⚠️ 复杂度分析：

时间复杂度：O(10^n) —— 需要检查每个数字
空间复杂度：O(n) —— 数字转字符串的存储开销

3.2. 组合数学解法

通过数学优化，我们可以大幅提升效率。核心思路是利用排列组合原理计算满足条件的数字个数，而非逐个检查。

关键观察点：

n=0 时：只有 0 满足条件 → 返回 1
n=1 时：0-9 共 10 个数字
n>1 时：
- 第一位：9 种选择（1-9，不能为 0）
- 第二位：9 种选择（0-9 排除第一位）
- 第三位：8 种选择，依此类推

基于排列原理的优化实现：

int combinatorial(int n) {
    if (n == 0) return 1;
    
    int result = 10;  // 个位数情况
    int current = 9;  // 当前位数的组合数
    int available = 9; // 剩余可用数字

    for (int i = 2; i <= n; i++) {
        current *= available;
        result += current;
        available--;
    }
    return result;
}

验证测试用例：

@Test
void givenNumber_whenUsingCombinatorial_thenCountNumbersWithUniqueDigits() {
    assertEquals(91, UniqueDigitCounter.combinatorial(2));
}

✅ 复杂度分析：

时间复杂度：O(n) —— 仅需遍历位数
空间复杂度：O(1) —— 仅使用少量变量

4. 结论

本文对比了两种统计不重复数字的方案：

暴力解法：简单粗暴但效率低下，仅适用于极小规模（n≤3）
组合数学解法：通过排列原理将复杂度降至 O(n)，是生产环境的首选

当处理大规模数据时（如 n>8），组合解法的优势尤为明显。实际开发中应优先选择数学优化方案，避免踩性能坑。

Persistence

REST

Security