Hard

题目描述

给定一个整数 n，返回在范围 [1, n] 中至少有一位重复数字的正整数的个数。

示例 1：

输入：n = 20
输出：1
解释：只有一个正数（<= 20）至少有 1 位重复数字：11。

示例 2：

输入：n = 100
输出：10
解释：至少有 1 位重复数字的正数（<= 100）有：11, 22, 33, 44, 55, 66, 77, 88, 99, 和 100。

示例 3：

输入：n = 1000
输出：262

约束条件：

  • 1 <= n <= 10^9

提示：

  • 有多少个没有重复数字的数？有多少个 K 位数且没有重复数字？
  • 有多少个与 N 长度相同的数？有多少个与 N 前缀相同的数？

解题思路

这道题可以使用逆向思维：先计算没有重复数字的数的个数，然后用总数减去它就得到了至少有一位重复数字的数的个数。

核心思路

  1. 计算无重复数字的个数：

    • 对于位数小于 n 的数字：使用排列组合计算
    • 对于位数等于 n 的数字：使用数位 DP 的思想逐位计算

  2. 分两部分统计：

    • 位数更少的数字：1位数有9个(1-9)，2位数第一位有9种选择(1-9)，第二位有9种选择(0-9除去第一位)，以此类推
    • 位数相同的数字：从高位到低位，考虑每一位可以选择的数字个数

具体算法

  1. 首先将 n 转换为字符串获取各位数字
  2. 计算位数小于 n 的所有无重复数字的个数
  3. 计算位数等于 n 且小于等于 n 的无重复数字的个数
  4. 用 n 减去无重复数字的总个数

时间复杂度主要取决于 n 的位数，空间复杂度为常数级别。这是一道典型的数位 DP 问题的变种。

代码实现

class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        string s = to_string(n + 1);
        int len = s.length();
        
        // 计算无重复数字的个数
        int uniqueCount = 0;
        
        // 计算位数小于len的数字个数
        for (int i = 1; i < len; i++) {
            uniqueCount += 9 * permutation(9, i - 1);
        }
        
        // 计算位数等于len且小于n+1的数字个数
        unordered_set<int> used;
        for (int i = 0; i < len; i++) {
            int digit = s[i] - '0';
            int smaller = 0;
            
            for (int d = (i == 0 ? 1 : 0); d < digit; d++) {
                if (used.find(d) == used.end()) {
                    smaller++;
                }
            }
            
            uniqueCount += smaller * permutation(9 - i, len - i - 1);
            
            if (used.find(digit) != used.end()) {
                break;
            }
            used.insert(digit);
        }
        
        return n - uniqueCount;
    }
    
private:
    int permutation(int n, int r) {
        if (r == 0) return 1;
        int result = 1;
        for (int i = 0; i < r; i++) {
            result *= (n - i);
        }
        return result;
    }
};

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n + 1)
        length = len(s)
        
        # 计算无重复数字的个数
        unique_count = 0
        
        # 计算位数小于length的数字个数
        for i in range(1, length):
            unique_count += 9 * self.permutation(9, i - 1)
        
        # 计算位数等于length且小于n+1的数字个数
        used = set()
        for i in range(length):
            digit = int(s[i])
            smaller = 0
            
            start = 1 if i == 0 else 0
            for d in range(start, digit):
                if d not in used:
                    smaller += 1
            
            unique_count += smaller * self.permutation(9 - i, length - i - 1)
            
            if digit in used:
                break
            used.add(digit)
        
        return n - unique_count
    
    def permutation(self, n: int, r: int) -> int:
        if r == 0:
            return 1
        result = 1
        for i in range(r):
            result *= (n - i)
        return result

public class Solution {
    public int NumDupDigitsAtMostN(int n) {
        string s = (n + 1).ToString();
        int length = s.Length;
        
        // 计算无重复数字的个数
        int uniqueCount = 0;
        
        // 计算位数小于length的数字个数
        for (int i = 1; i < length; i++) {
            uniqueCount += 9 * Permutation(9, i - 1);
        }
        
        // 计算位数等于length且小于n+1的数字个数
        HashSet<int> used = new HashSet<int>();
        for (int i = 0; i < length; i++) {
            int digit = s[i] - '0';
            int smaller = 0;
            
            int start = i == 0 ? 1 : 0;
            for (int d = start; d < digit; d++) {
                if (!used.Contains(d)) {
                    smaller++;
                }
            }
            
            uniqueCount += smaller * Permutation(9 - i, length - i - 1);
            
            if (used.Contains(digit)) {
                break;
            }
            used.Add(digit);
        }
        
        return n - uniqueCount;
    }
    
    private int Permutation(int n, int r) {
        if (r == 0) return 1;
        int result = 1;
        for (int i = 0; i < r; i++) {
            result *= (n - i);
        }
        return result;
    }
}

var numDupDigitsAtMostN = function(n) {
    function countUniqueDigits(digits, used, tight, pos) {
        if (pos === digits.length) return 1;
        
        let result = 0;
        let limit = tight ? parseInt(digits[pos]) : 9;
        
        for (let digit = 0; digit <= limit; digit++) {
            if (used & (1 << digit)) continue;
            
            let newUsed = used;
            let newTight = tight && (digit === limit);
            
            if (used !== 0 || digit !== 0) {
                newUsed |= (1 << digit);
            }
            
            result += countUniqueDigits(digits, newUsed, newTight, pos + 1);
        }
        
        return result;
    }
    
    let digits = n.toString();
    let totalUnique = countUniqueDigits(digits, 0, true, 0) - 1;
    
    return n - totalUnique;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

说明：

  • 时间复杂度：主要取决于数字 n 的位数，为 O(log n)
  • 空间复杂度：需要存储已使用的数字集合，最多 10 个数字，实际为 O(log n)

相关题目