切換
舊版
前往
大廳
主題

ZeroJudge - e666: 108 p4. 排序問題 解題心得

Not In My Back Yard | 2020-08-18 00:00:04 | 巴幣 0 | 人氣 233

題目連結:


題目大意:
第一列給定兩正整數 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,此時「被」加總的字母即是目標字母。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
" 迴圈加總 A 、 B 、 C 、…… 的數量直到 ≧ M "
這邊可以用前綴和+二分法( lower_bound() )來加速,不過因為字母只有26個差異不大就是
2020-08-18 09:57:59
Not In My Back Yard
沒錯,所以我只有把核心思維陳述出來,而沒有提及程式碼裡有的前綴和(因為真的差不了多少)。
2020-08-18 12:45:13

更多創作