[HackerRank]計數排序3(Counting Sort 3)


題目描述

一個已排序的清單,用來作為排序依據的元素常常只是其他值的某個鍵值或是屬性。舉例來說,如果您正在根據檔案大小來排序檔案,檔案的大小必須跟它們所對應的檔案互相連結。您不能只單純地排序檔案大小,然後將其輸出,您會需要輸出跟這些檔案有關的必要資訊。如果您真的不需要其他資訊,您可以簡單的排序那些數值就好,這也可以讓計數排序變得更加容易。您只要已經計算過清單中數值出現的次數,就不用再去存取原本的清單。然而,當您需要其他資訊的時候,您還是需要去存取原本的元素。給定一個包含整數和字串的陣列,請分別計算並輸出整數小於或等於0到99(包含0和99)的元素數量。

原題網址

https://www.hackerrank.com/challenges/countingsort3

輸入格式

第一行是陣列的大小N,範圍在100到106之間(包含100和106)。接下來的N行每行都是由一個整數和一個字串組成的陣列元素,整數範圍在0到100之間(包含0,但不包含100),字串長度在1到10之間(包含1和10)。

輸出格式

分別計算並輸出整數小於或等於0到99(包含0和99)的元素數量,用空白字元分隔。

範例輸入

10
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the

範例輸出

1 3 5 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

額外解釋

「0」出現了1次,所以輸出「1」。「0」和「1」共出現3次,所以輸出「3」。「0」、「1」、「2」共出現5次,所以輸出「5」。依此類推,共會輸出100個累計數量。

解題概念

這個題目不同的是,此題需要另外在計數時將字串儲存到另一個陣列之對應位置上(之後排序時會用到),並在輸出數量時進行累加的動作。

參考答案

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章