b330 - NOIP2013 1.记数问题

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在 1 到 n 的所有整數中，數字 x (0 ≤ x ≤ 9) 總共出現了多少次。

解題思路

題目要求統計指定數字在一個範圍內出現的次數。程式碼透過迴圈迭代 1 到 n 的每個數字，並對每個數字進行位元分解，統計每個位元上出現目標數字 x 的次數。使用一個陣列 a 來儲存每個數字 (0-9) 出現的次數，最後輸出陣列中對應於 x 的元素。

複雜度分析

• 時間複雜度: O(n * log(n))
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	int n,x;
	while(cin >> n >> x){
		int a[10]={0},num=1;
		for(int i=1;i<=n;i++){
			num=i;
			while(num!=0){
				a[num%10]++;
				num/=10;
			}
		}
		cout << a[x] << "\n";
	}
}