e618 - 00484 - The Department of Redundancy Department
題目描述
題目要求讀取一串整數序列，並輸出每個整數出現的次數，按照輸入的順序排列。重複的數字只輸出一次，並記錄其出現的總次數。
解題思路
這題的核心是統計每個數字出現的頻率，並按照輸入的順序輸出。程式使用了一個大小為 101 的 ans 結構體陣列 a 來儲存數字及其出現次數。對於每個輸入的數字 c，程式會遍歷 a 陣列，如果找到相同的數字，則將其出現次數加 1；如果沒有找到，則將數字儲存到 a 陣列中，並將其出現次數初始化為 1。最後，程式遍歷 a 陣列，輸出所有出現過的數字及其對應的出現次數。
複雜度分析
- 時間複雜度: O(N*M)，其中 N 是輸入數字的個數，M 是
a陣列的大小 (101)。在最壞的情況下，需要遍歷整個a陣列來查找或插入每個數字。 - 空間複雜度: O(M)，其中 M 是
a陣列的大小 (101)。程式使用了一個固定大小的陣列來儲存數字及其出現次數。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
struct ans{
int n,time;
};
int c;
ans a[101];
int main(){
while(scanf("%d",&c)>0){
for(int i(0);i<100;++i){
if(a[i].time==0){
a[i].n=c;
a[i].time=1;
break;
}
else if(a[i].n==c){
++a[i].time;
break;
}
}
}
for(int i(0);i<100;++i){
if(a[i].time==0)break;
printf("%d %d\n",a[i].n,a[i].time);
}
}