d885 - NOIP2007 1.統計數字 番外篇
題目描述
題目要求讀取一組自然數，統計每個自然數出現的次數，並按照自然數從小到大的順序輸出每個自然數及其出現次數。
解題思路
本題可以使用 Hash Table (具體實作為 C++ 的 map) 來統計每個數字的出現次數。map 能夠自動按照 key (也就是數字) 的大小進行排序。程式首先讀取數字的個數 n，然後讀取 n 個數字，並使用 map 記錄每個數字出現的次數。最後，遍歷 map，按照 key 的順序輸出每個數字及其對應的次數。
複雜度分析
- 時間複雜度: O(n log n) (
map的插入和查找操作平均時間複雜度為 log n，總共進行 n 次操作) - 空間複雜度: O(k) (k 為不相同數字的個數，最壞情況下 k = n)
程式碼
#include <iostream>
#include <map>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
long long int a,b;
map <int,int> ans;
map <int,int> ::iterator iter;
cin >> a;
while(a--){
cin >> b;
(ans.find(b)==ans.end())?ans[b]=1:ans[b]++;
}
for(iter=ans.begin();iter!=ans.end();iter++){
cout << iter->first << " " << iter->second << "\n";
}
}