2

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

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

我在幼稚中使用的方法，即 nlogn（通过查看复杂性很容易猜到方法:)）

4

1 回答 1

4

以下算法非常有效地计算从 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 4 a 3 a 2 a 1 a 0演示该算法。

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

  • 我0 : 一4一3一2一1 0 <= 我 < 一4一3一2一1一0
  • 我1 : 一4一3一2 0 0 <= 我 < 一4一3一2一1 0
  • 我2 : 一4一3 0 0 0 <= 我 < 一4一3一2 0 0
  • 我3 : 一4 0 0 0 0 <= 我 < 一4一3 0 0 0
  • 我4 : 0 0 0 0 0 <= 我 < 一个4 0 0 0 0

在十进制表示中没有“3”的区间 I j中的整数个数是

  • 0，如果较高值的数字 a j+1， a j+2，... 之一等于 3，否则：
  • a j * 9 j，如果 0 <= a j <= 3，（第 j个数字有j个选择，所有低值数字有 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;
}
于 2013-01-14T09:01:21.070 回答