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

Question

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

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

我天真的使用的方法，即 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₁a₂a₁ sub>a₀.

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

• I₀: a₄a₃a₂a₁ 0 <= i < a₄a₃a₂a₁a₀
• I₁: a₄a₃a₂ 0 0 <= i < a ₄a₃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^th 个数字，所有低值数字有 9 个选择)，
• (a_j - 1) * 9^j，如果 aj > 3(因为 3 不是第 j 的有效选择数字)。

所以我们有如下函数:

/*
 * 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;
}