d885v2 - Error

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一串整數，並統計每個整數出現的次數，最後輸出每個整數及其出現次數。

解題思路

使用 map 資料結構來儲存每個整數及其對應的出現次數。map 能夠自動排序鍵，因此輸出的結果也會是排序過的。程式首先讀取整數的數量 n，然後迴圈讀取 n 個整數，並使用 map 統計每個整數的出現次數。最後，迴圈遍歷 map，輸出每個整數及其出現次數。

複雜度分析

• 時間複雜度: O(n log n) (主要來自 map 的插入和遍歷，map 的插入和查找操作平均時間複雜度為 log n，遍歷 map 的時間複雜度為 n)
• 空間複雜度: O(n) (最壞情況下，所有輸入的整數都不同，map 需要儲存 n 個鍵值對)

程式碼

#include <iostream>
#include <map>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
    int n,in;
    cin >> n;
    map<int,int> mp;
    while(n--){
		cin >> in;
        mp[in]++;
    }
    for(auto it: mp)
        cout << it.first << ' ' << it.second << endl;
}