題目連結:
題目大意:
第一列給定兩正整數 N 、 M (N ≦ 10000000,1 ≦ M ≦ 10),代表有 N 個大寫字母等著排序(依照字典序),並且要從排序後的字母找出 M 個字母。接著一列給定 N 個大寫英文字母,代表要排序的字母們。最後一列給定 M 個整數(皆小於等於 N),代表要依序輸出的目標字母所在位置。
範例輸入:
輸入範例一:
20 4
KFGHTHZHJKGXAKMCNHTE
5 1 15 3
輸入範例二:
15 9
XOMWSMNQLOAENTO
3 9 12 1 3 1 5 9 12
範例輸出:
輸出範例一:
GAME
輸出範例二:
LOSALAMOS
解題思維:
雖然將所有字元直接排序然後找相對應位置的字元並輸出是可行的。但是也可以節省儲存整條字串的空間以及排序的時間,只需用數的。因為大寫英文字母只有 26 個,因此就直接數輸入的字串裡有多少個 A 、 B 、 C 、 …… 即可完成「排序」(由 A 掃到 Z 就等同於將原字串排序,這種用數的排序之演算法稱作計數排序法(Counting Sort))。
數完之後可以迴圈加總 A 、 B 、 C 、…… 的數量直到 ≧ M,此時「被」加總的字母即是目標字母。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。