切換
舊版
前往
大廳
主題

ZeroJudge - d587: 參貳壹真好吃 解題心得

Not In My Back Yard | 2018-09-18 21:06:09 | 巴幣 0 | 人氣 275

題目連結:


題目大意:
給定N(N ≦ 1, 000, 000),代表接下來有N個數字。每個數字只會是1、2或3。

把給定的N個數字由小排到大輸出。


解題思維:
雖然這題可以直接呼叫內建的sort()函式,就可以過了。

但是現在要介紹一下一個排序的演算法,叫做——Counting Sort。

顧名思義,用數的去「排序」。有時候已知數字的範圍,就可以直接開相應大小的陣列(當然,太大就不適用了),然後出現什麼數字就把在相應陣列位置的值+1(本來都是0)。

然後在輸入結束後,用迴圈由小跑到大的數字(因為範圍已知)。有曾經出現過的數字,就輸出相應的次數。

雖然這演算法會消耗不少記憶體空間,但是在時間層面確實是數一數二地快(跟資料數量N和範圍M成正比,即時間複雜度為O(N+M)),並不失為一個好的排序手段。



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

創作回應

更多創作