d578 - 小涵的積木
題目描述
題目描述了小涵有許多組相同的積木，每塊積木上都有文字。她不小心弄丟了一塊積木，現在給定剩下的積木上的文字，要求找出丟失的那塊積木上的文字。輸入包含積木組數 n 和積木組合數 m，以及剩餘積木上的文字。
解題思路
這題的核心思想是利用模數運算來找出丟失的積木。如果 n * m 比較小，可以直接使用 map 統計每個字串出現的次數，然後找出出現次數不是 m 的倍數的字串，這個字串就是丟失的積木。如果 n * m 比較大，則使用一個二維陣列 buffer 統計每個字元在每個位置出現的次數，然後找出第一個出現次數不是 m 的倍數的字元，並將其組合成丟失的積木字串。
複雜度分析
- 時間複雜度: O(nmk) 其中 k 是字串的平均長度。在
n*m較小的情況下，map 的操作佔主導，時間複雜度接近 O(nmk)。在n*m較大的情況下，遍歷 buffer 陣列的時間複雜度為 O(1000*128)，可以視為常數時間。 - 空間複雜度: O(nm) 或 O(1000128)。在
n*m較小的情況下，map 的空間複雜度為 O(nm)。在n*m較大的情況下，buffer 陣列的空間複雜度為 O(1000128)，可以視為常數空間。
程式碼
#include <iostream>
#include <map>
using namespace std;
long long int n,m,type2=1001*129,buffer[1001][129];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> m){
if(n==0&&m==0)break;
long long int k=n*m-1;
string a;
if(type2>=k){
map <string,int> s;
map <string,int> ::iterator i;
getline(cin,a);
while(k--){
getline(cin,a);
++s[a];
}
for(i=s.begin();i!=s.end();++i){
if(i->second%m){
cout << i->first << "\n";
break;
}
}
}
else{
getline(cin,a);
string rt;
while(k--){
getline(cin,a);
int al=a.length();
for(int i=0;i<al;++i){
++buffer[i][a[i]];
}
}
for(int i=0;i<1000;++i){
int s=0;
for(int j=0;j<128;++j){
if(buffer[i][j]%m){
rt+=(char)j;
s=1;
break;
}
}
if(s==0)break;
}
cout << rt << "\n";
}
}
}