✏️ 纠错
第 160 题 / 共 201 题
第9题 下面的 sum_digit函数试图求出从1到n(包含1和n)的数中,包含数字d的个数。该函数的时间复杂度为( )。
#include <string>
int count_digit(int n, char d) {
int cnt = 0;
std::string s = std::to_string(n);
for (int i = 0; i < s.length(); i++)
if (s[i] == d)
cnt++;
return cnt;
}
int sum_digit(int n, char d) {
int sum = 0;
for (int i = 1; i <= n; i++)
sum += count_digit(i, d);
return sum;
}你真棒!
📝 题目解析
答案:A
考纲知识点:
解析:count_digit()和位数相关,对n,位数为log10(n),主函数为n次for循环,总体复杂度O(nlogn)