UVa 755

題目

http://domen111.github.io/UVa-Easy-Viewer/?755

有 $n$ 個電話號碼，我們規定一個電話號碼的標準格式是 3個數字 - 4個數字

例如 1234-567 就是一個合法的電話號碼

另外，我們的撥號鍵都會有相對應的英文字母，有時候我們也會用這些英文字母來記憶電話號碼

至於 - 開心放多少個就放多少個，但是合法的電話號碼表示中只會在第 3 和第 4 個數字之間有 -

現在給你很多雜亂的電話號碼，請你幫忙全部轉換成合法的電話號碼格式，並且找出重複出現的電話號碼分別都是現了幾次

想法 By Koios

轉換成合法字串並不困難，我們可以先忽視其中的所有 - ，當數字到了 3 個之後再自行加入

並且把所有的英文字母轉換成相對應的數字即可

轉換成合法字串後，要找到重複的字串可以用排序來解決

排序後的序列，會使得相同的字串會被排在一起，那麼我們就只需要再掃過檢查重複即可

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int t, n;
bool out=false;
// 字串輸入到 s 經過處理放入 arr
string s, arr[100010];
// 從 A~Z 分別對應的數字建立起來
string tbl = "22233344455566677778889999";
int main(){
	cin>>t;
	while(t--){
		if(out) cout<<"\n";
		else out=true;
		
		cin>>n;
		for(int i=0 ; i<n ; i++){
			cin>>s;
			// 記得要先初始化
			arr[i] = "";
			
			for(int j=0, k=0 ; j<s.size() ; j++){
				// 我們只在乎不是 - 的字元
				if(s[j] != '-'){
					if(s[j]>='0' && s[j]<='9') arr[i] += s[j];
					else if(s[j]>='A' && s[j]<='Z') arr[i] += tbl[s[j]-'A'];
					// 自己加上 -
					k++;
					if(k == 3) arr[i] += '-';
				}
			}
		}
		
		sort(arr, arr+n);
		
		bool find_ans=false;
		// i 是當前關注的對象
		// j 是要和 i 比較的對象
		for(int i=0, j ; i<n ; i=j){
			for(j=i+1 ; j<n ; j++){
				// 找到第一次不相同的位置
				if(arr[i] != arr[j]) break;
			}
			if(j != i+1){
				cout<<arr[i]<<" "<<j-i<<"\n";
				find_ans=true;
			}
		}
		if(!find_ans)
			cout<<"No duplicates.\n";
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

每筆測資預處理 $arr$ 時間複雜度為 $O(\sum_{i=0}^{n-1}{len(s)})$

每筆測資排序時間複雜度為 $O(nlogn)$

每筆測資找重複元素的時間複雜度為 $O(n)$

總時間複雜度為 $t(2n + nlogn + \sum_{i=0}^{n-1}{len(s)})$