c012 - 10062 - Tell me the frequencies!

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取多行字串，並針對每一行字串，統計每個字元的出現次數。輸出時，按照出現次數由小到大排序，若出現次數相同，則按照字元的 ASCII 值由大到小排序。每行輸出字元的 ASCII 值和其出現次數，並在每組測試資料之間空一行。

解題思路

此題的核心在於統計字元頻率，並按照特定規則排序輸出。程式使用一個大小為 127 的整數陣列 b 來儲存每個 ASCII 字元的出現次數。遍歷輸入字串，將每個字元的對應陣列元素加一。統計完所有字元的頻率後，使用巢狀迴圈按照出現次數由小到大，ASCII 值由大到小排序輸出。外層迴圈遍歷出現次數 (1 到 1000)，內層迴圈從 ASCII 值 126 遞減到 0，檢查每個字元的出現次數是否等於當前出現次數。如果相等，則輸出該字元的 ASCII 值和出現次數。

複雜度分析

• 時間複雜度: O(N * M * K)，其中 N 是輸入字串的數量，M 是每個字串的長度，K 是 ASCII 值的範圍 (127)。外層迴圈迭代最多 1000 次，內層迴圈迭代 127 次，字串遍歷 M 次。
• 空間複雜度: O(1)，因為使用的陣列 b 大小固定為 127，不隨輸入大小變化。

程式碼

#include <bits/stdc++.h>
using namespace std;
int main(){  
	cin.tie(0); ios::sync_with_stdio(false);
    string a;  
    bool s=0;
    while(getline(cin,a)){
		if(s!=0)cout << "\n";
		else s=1;  
        int b[127]={0};  
        for(int i=0;i<127;i++)
        	b[i]=0;
        for(int i=0,al=a.length();i<al;i++)  
            b[a[i]]++;  
        for(int i=1;i<=1000;i++)  
            for(int j=126;j>=0;j--)  
                if(b[j]==i)cout << j << " " << i << "\n";  
    }  
}