2376. Count Special Integers

Created 08/14/2022

We call a positive integer special if all of its digits are distinct.

Given a positive integer n, return the number of special integers that belong to the interval [1, n].

Example 1:

Input: n = 20
Output:
 19
Explanation:
 All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.

Example 2:

Input: n = 5
Output:
 5
Explanation:
 All the integers from 1 to 5 are special.

Example 3:

Input: n = 135
Output:
 110
Explanation:
 There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.

Constraints:

• 1 <= n <= 2 * 109

Basic Idea

静下心来，分情况讨论，计算总共的数字个数。

1. 首先考虑位数小于n的所有数字，这种情况下对于使用什么数字完全没有限制，只需要保证不重复即可。如果n=1234，则共有 9*9*8 + 9*9 + 9 个满足条件的三位以下的数字。

2. 接下来考虑位数和n相同的情况：

   1. 对第i位考虑该位小于n中第i位的情况，这种情况下剩余的位可以任意取值

   2. 之后考虑第i位和n中第i位相同的情况，此时需要将该数字标记为已经使用，然后继续考虑后面一位

Java Code:

class Solution {
    public int countSpecialNumbers(int n) {
        n = n + 1; // 将 [1,n] 转化为 [1, n + 1) 的问题
        List<Integer> list = new ArrayList<>();
        while (n != 0) {
            list.add(n % 10);
            n /= 10;
        }
        Integer[] arr = list.stream().toArray(Integer[]::new);
        int nd = arr.length;
            
        int ret = 0;
        
        // 位数i小于n的满足条件数字个数 (test: 1000->738)
        for (int i = 1; i < nd; ++i) {
            // 最高位不能取0
            ret += 9 * A(9, i - 1);
        }
        
        // 位数等于n的满足条件数字个数
        Set<Integer> used = new HashSet<>(); // 1-9 的数字中，哪些已经被确定用掉
        for (int i = nd - 1; i >= 0; --i) {
            // 最高位i小于n中对应数字的满足条件数字个数
            if (i == nd - 1) {
                if (arr[i] > 1) {
                    ret += (arr[i] - 1) * A(9, i);
                }
            } else {
                for (int j = 0; j < arr[i]; ++j) {
                    if (!used.contains(j)) {
                        ret += A(9 - used.size(), i);
                    }
                }
            }
            if (used.contains(arr[i])) {
                // n中第i位已经被用掉，所以该位取不到相等，ret已经包含所有结果个数
                return ret;
            }
            used.add(arr[i]); // 确定第i位和n中相等，然后继续考虑更低位
        }
        
        return ret;
    }
    
    private int A(int n, int m) {
        if (m == 0) return 1;
        return A(n, m - 1) * (n - m + 1);
    }
}