c - 我怎样才能算出一个数字中有多少个字符？

Question

所以长度为:

int test1 = 1 是 1 个字符长

int test2 = 37 是 2 个字符长

int test3 = 82342 长度为 5 个字符。

---

我可以找到这些 int 的字符长度:

int character_len = floor(log10(abs(whatever_vairable_here))) + 1;

---

我想一直计算 int i = 1; 直到 n，但是在示例代码中，我只使用了 20 ).有没有一种方法可以计算出我将使用的字符总数，而无需使用第一个 while 循环来确定我必须 malloc 的大小。我想弄清楚我应该用多少空间 malloc

int total_characters_needed = 0;
int i = 1;
while (i <= 20) {
    total_characters_needed += floor(log10(abs(i))) + 1;`
    i++;
}

char *my_numbers_as_a_string = malloc(sizeof(char) * total_characters_needed);

i = 1;
while (i <= 20) {
    sprintf(my_numbers_as_a_string, "%d", i);
    i++;
}

printf("%s\n", my_numbers_as_a_string);
// Should print out:
// 1234567891011121314151617181920
//
// If the above is unread-able its basically
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Answer 1

这更像是一个谜题。你想在字符串中存储从 1 到某个数字 x 的数字序列，所以需要所有字符的总和。 例如，设 x=77867。所以 x 是一个 5 个字符长的数字。这可以使用 user10334659 给出的循环找到。

首先要注意的是，从1到4位的数字基本上是填充的，不依赖于x的值。所以我们可以先计算出这些数字的字符数。

1. 1-9 :个位数。 #numbers = 9 。 => 字符 = 9 x 1
2. 10-99:2 个字符。 #numbers = 90. => 字符 = 90 x 2
3. 100-999:3 个字符。 # 数字 = 900。=> 字符 = 900 x 3
4. 1000-9999:4 个字符。 # 数字 = 9000。=> 字符 = 9000 x 4

所以从 1 到最大 y 位数的所有数字的总字符数是:

9 ( 10^0 x 1 + 10^1 x 2 + ... + 10^(y-1) x y )

现在我们只需要计算从 10^(y) 到 x(这是一个 (y+1)- 位数)的总数。对于我们的例子，10000 - 77867:#numbers = 67688 => characters = 67688x5。

时间复杂度

设最大数目为n。然后y+1可以在O(log(n))时间内计算出来。查找从 1 到 y 位数的字符也需要 O(log(n)) 时间。最后，在 O(1) 时间内找到了从 10^y 到 n 的字符数。

所以这个算法可以在 O(log(n)) 时间内找到字符总数，而不是简单的 O(n) 时间循环。