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


題目描述

快速排序法的時間複雜度為O(nlog2n),還有什麼演算法可以排序更快呢?一般來說,大部分的演算法都需要進行「比較」,所以在最差的案例下最快也是需要nlog2n的執行時間。然而在某種類型的輸入條件下,使用「非比較」的演算法會更有效率,只需要線性時間就可以完成計算。給定一個整數陣列,請算出各數值出現的次數。

原題網址

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

輸入格式

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

輸出格式

個別輸出數字0到99(包含0和99)的出現次數,用空白字元分隔。

範例輸入

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

範例輸出

0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2

額外解釋

「0」出現了0次,「1」出現了2次,「2」出現了0次,依此類推。

解題概念

宣告並實體化出一個長度為100的整數陣列,預設元素數值均為0。緊接著從標準輸入中讀入陣列內容,並同時利用那個長度為100的整數陣列統計0到99數字出現的次數。最後再把那個長度為100的整數陣列輸出。

參考答案

關於作者

Magic Len

Magic Len

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

相關文章