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

題目描述

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

原題網址

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

輸入格式

輸入有兩行,第一行是陣列的大小,範圍在100到106之間(包含100和106)。第二行是整數陣列的內容,用空白字元分開各個整數,整數範圍在0到100之間(包含0,但不包含100)。

輸出格式

使用計數排序排序陣列後依序輸出陣列中的元素,用空白字元分隔。

範例輸入

100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33

範例輸出

1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 46 46 48 50 53 56 56 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99

解題概念

根據這個題目所解答出來的程式,我們可以得知陣列中各個元素的出現次數,接著就可以直接利用這個次數,來將元素數值從小到大依序、依次輸出,就是陣列排序後的結果了。舉例來說,假設陣列有3個「2」,2個「1」,不管元素在原始陣列中的順序是怎樣,既然我們已經知道每個元素的出現次數,輸出時就先輸出2個「1」,再輸出3個「2」,就是陣列最終排序後的結果了。

參考答案

關於作者

Magic Len

Magic Len

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

相關文章