題目連結:
題目大意、範例輸入、範例輸出:
與
昨天的題目差不多,只是N的範圍變為10 ^ 6了。
解題思維:
在
昨天的文章裡,提到了「堆積」這個資料結構。我們將其用於快速找出兩個最小值。時間複雜度是 O(N * log N)。
乍看之下很優秀,但是要考慮到會有很多筆的「 N 值」,所以時間複雜度為O(T * N * log N)。在前兩題可以輕鬆地通過,但是在這題則不行。(因為 N 值可以到 10 ^ 6)
因此,今天要講另一個方法——「佇列」:
我們可以觀察出,因為我們每次都是挑目前最小的數字相加,因此相加後產生的新數字必定是遞增的。
而現在假設有兩個佇列(Queue),一個存已排序(由小到大)的原始資料(Q1),另一個存兩兩相加的和(Q2)。因為上述的性質,所以Q2裡的數字也是有序的(由小到大)。
而兩個佇列因為都是有序的,因此要抓兩個最小值非常容易,直接從兩個佇列的前端抓就好(但是要小心佇列可能為空,可能最小的不只一個,最小的都是某一個佇列等等……)
總結以上,我們存取兩個最小值的時間複雜度為 O(1) 。且有N個數字,所以會做 N - 1 次的加法。因此總體時間複雜度為 O(N)。
但是我們假定了原始資料已經排序過,而在這題並不一定如此。但是幸好這題的那 N 個數字都不會超過 10 ^ 6 。因而可以使用 Counting Sort(其實使用 Radix Sort 比較好,但是本人當時沒想到,而現在又懶得改(? )。
Counting Sort,正如其名,就是用數的。出現幾個1,就存1的數量、幾個2,就把2的數量存起來,以此類推。
然後從 1 開始跑到 10 ^ 6 (這題數字可能的範圍),把出現數量 > 0 的數字依照數量抓出來,就排序完畢了。
以上,時間複雜度 O(K + N ), K 是數字出現的範圍大小,這題是 10 ^ 6 。
因此,本人在本題使用的演算法的總體時間複雜度為O(T * ( N + K ))。但是實際上是可以再加強的,使用
基數排序(Radix Sort)的話, K 值會降到 7 左右,是個高效的算法。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。