1~n 之间 数字x出现的次数

声明： 仅个人小记

暴力法

/* 输入： n 整数， 0 =< x <= 9 输出： 1~n 中 数字x出现的次数 */ #include <iostream> #include <ctime> using namespace std; int main(void) { clock_t startTime, endTime; int n, x; cin >> n >> x; startTime = clock(); int t; int cnt = 0; for (int i = 1; i <= n; i ++) { t = i; while (t) { if (t%10 == x) cnt ++; t /= 10; } } endTime = clock(); cout << cnt << endl; cout << "time elpased: " << double(endTime-startTime) *1000 /CLOCKS_PER_SEC << "ms" << endl; cout << endTime-startTime << endl; return 0; }

优化

/* 效率极大提升，算法耗费时间仅仅和给定的整数的长度有关 */ #include <iostream> #include <ctime> using namespace std; int main(void) { int n, x; cin >> n >> x; int startTime, endTime; startTime = clock(); int t; int cnt = 0; int k = 1; int a; int b = n; while (b) { a = b % 10; b = b / 10; cnt += b * k; if (a > x) cnt += k; else if (a == x) cnt += (n%k+1); k *= 10; } if (x == 0) { // x == 0 时，不一样的地方是 我们都知道 01 02 03 不算是两位数， 001 002 003 不算是三位数， 所以减去 (100+10) cnt --;// 因为起点是 1 不是 0， 所以个位上的0 少了一个 int p = 10; int q = 0; while (n/10) { q += p; p *= 10; n/=1; } cnt -= q; } endTime = clock(); cout << cnt << endl; cout << "time elpased : " << (double)(startTime-endTime)*1000/CLOCKS_PER_SEC << "ms"<<endl; return 0; }

时间花费对比

0;