e809 - 1.字母排序 (Letters)
題目描述
題目要求根據給定的字母順序規則，對一個字串進行排序，並針對指定的索引位置輸出排序後的字串中的字母。
解題思路
首先，讀取自定義的字母順序規則，並使用一個陣列 a 記錄每個字母出現的次數。然後，讀取待排序的字串，遍歷字串中的每個字母，並在 a 陣列中找到該字母的出現次數，將該字母添加到結果字串 ans 中，同時減少 a 陣列中該字母的出現次數。最後，根據題目要求，輸出指定索引位置的字母。
複雜度分析
- 時間複雜度: O(S + N + Q)，其中 S 是待排序字串的長度，N 是自定義字母順序的長度，Q 是查詢次數。
- 空間複雜度: O(1)，因為
a陣列的大小固定為 27，ans字串的最大長度為 S。
程式碼
#include <iostream>
using namespace std;
int a[27],n,tp;
string ans,aa,tmp;
int main(){
cin >> aa;
cin >> tmp;
cin >> n;
int tmpl=tmp.length(),aal=aa.length();
for(int i=0;i<tmpl;++i){
++a[tmp[i]-'A'];
}
for(int i=0;i<aal;++i){
int ai=aa[i]-'A';
while(a[ai]--){
ans+=ai+'A';
}
}
while(n--){
cin >> tp;
cout << ans[tp-1] << "\n";
}
}