algorithm - 编程: Give the count of all such numbers which have 3 in their decimal representation

Question

给定一个数字 n，编写一个函数，返回从 1 到 n 的数字计数，这些数字的十进制表示形式中不包含数字 3

解决这个问题的最佳方法是什么。

我在 naive 中使用的方法，即 nlogn (通过查看复杂性很容易猜测该方法:))

Answer 1

以下算法非常有效地计算从 0 到 (n-1) 的十进制表示中不含“3”的整数的数量。 (我将间隔从 1 .. n 修改为 0 .. n-1 只是为了稍微简化以下计算。)

(我不是复杂度计算方面的专家，但我认为这个算法的复杂度是 O(log n) ，因为它对 n 的每个数字执行固定数量的步骤。)

第一个观察结果是，最多有 d 位的整数(即区间 0 .. 10^d-1 中的数字)的十进制表示中不包含数字 3 的整数正好是9^d，因为对于每个数字，您有 9 个可能的选择 0,1,2,4,5,6,7,8,9。

现在让我用 5 位数字演示该算法 n = a₄a₃a₂a_1a<子>0。

我们分别计算间隔的十进制表示中不包含“3”的整数的数量

• I₀:a₄a₃a₂a₁ 0 <= i < a₄a₃a₂a₁a₀
• I₁: a₄a₃a₂ 0 0 <= i 4a₃a₂a₁ 0
• I₂: a₄a₃ 0 0 0 <= i < a₄a₃a₂ 0 0
• I₃: a₄ 0 0 0 0 <= i < a₄a₃ 0 0 0
• I₄: 0 0 0 0 0 <= i < a₄ 0 0 0 0

区间 I_j 中不带“3”的十进制整数的个数为

• 0，如果较高值的数字 a_j+1、a_j+2、... 之一等于 3， 否则:
• a_j * 9^j，如果 0 <= a_j <= 3，(a_j的选择 第 j 位数字，所有较低值数字有 9 个选择)，
• (a_j - 1) * 9^j，如果 aj > 3(因为 3 不是第 j^th 的有效选择数字)。

所以我们有以下函数:

/*
 * Compute number of integers x with 0 <= x < n that do not
 * have a 3 in their decimal representation.
 */
int f(int n)
{
    int count = 0;
    int a;      // The current digit a_j
    int p = 1;  // The current value of 9^j

    while (n > 0) {
        a = n % 10;
        if (a == 3) {
            count = 0;
        }
        if (a <= 3) {
            count += a * p;
        } else {
            count += (a-1) * p;
        }
        n /= 10;
        p *= 9;
    }

    return count;
}