查詢指定區間第k大的值-有解無憂

n<100,000,共有1000,000次查詢，時間限制2000ms

uj5u.com熱心網友回復：

冒泡排序前k次回圈

uj5u.com熱心網友回復：

可以考慮用KD-tree實作，首先預處理，得到最大值,，復雜度為O(n)，然后，求其K近鄰，因為是一維的，復雜度為O(lgn*k)

uj5u.com熱心網友回復：

不完整的快排可以不？

uj5u.com熱心網友回復：

可以考慮離散化之后映射到1-100000，然后用可持久化線段樹查詢第K大（可持久化線段樹入門題區間第K大）

uj5u.com熱心網友回復：

劃分樹求解區間查詢第k大值問題，時間復雜度logN

uj5u.com熱心網友回復：

真搞不懂~主席樹裸題有什么好問的?

uj5u.com熱心網友回復：

參考 3 樓 yyfhz 的回復:

不完整的快排可以不？

可以。

我大概做過實驗，百萬以上的資料量，改后的排速度最快（也就是三樓說的不完整快排），比主席樹快（6樓的方法），更比堆排序快（很意外居然前幾樓沒人提到堆排序）。可能是因為主席樹空間復雜度比較高，所以耗時。

大概方法是快排砍半。時間復雜度LogN*Log(N-K)，空間復雜度是O(1)
本來的快排是：
第一步，分組。第二步，遞回排左邊。第三步，遞回排右邊。
3樓說的那個：
第一步，分組。第二步，分情況，如果分組的那個數<K，只遞回找左邊；如果分組的那個數>K，只遞回找右邊。

看起來好像和快排差不多，但實際上時間復雜度遠小于快排，因為每次分組之后都要砍半，每次砍半啊，不是1/2的時間。

另外，除了這種改裝快排，比較快的方法有主席樹時間復雜度理論上和快排砍半差不多。還有堆排序。
堆排序建堆還是比較快的，關鍵是堆排序把前面k的排好序了，后買雖然不需要排序，但也浪費了好多時間，k越大時間浪費越多。

uj5u.com熱心網友回復：

參考 7 樓 lx3275852 的回復:

Quote: 參考 3 樓 yyfhz 的回復:

不完整的快排可以不？

可以。

我大概做過實驗，百萬以上的資料量，改后的排速度最快（也就是三樓說的不完整快排），比主席樹快（6樓的方法），更比堆排序快（很意外居然前幾樓沒人提到堆排序）。可能是因為主席樹空間復雜度比較高，所以耗時。

大概方法是快排砍半。時間復雜度LogN*Log(N-K)，空間復雜度是O(1)
本來的快排是：
第一步，分組。第二步，遞回排左邊。第三步，遞回排右邊。
3樓說的那個：
第一步，分組。第二步，分情況，如果分組的那個數<K，只遞回找左邊；如果分組的那個數>K，只遞回找右邊。

看起來好像和快排差不多，但實際上時間復雜度遠小于快排，因為每次分組之后都要砍半，每次砍半啊，不是1/2的時間。

另外，除了這種改裝快排，比較快的方法有主席樹時間復雜度理論上和快排砍半差不多。還有堆排序。
堆排序建堆還是比較快的，關鍵是堆排序把前面k的排好序了，后買雖然不需要排序，但也浪費了好多時間，k越大時間浪費越多。

仔細想了想，時間復雜度可能算的不對，不是O(logN*log(N-K))，時間復雜度大概是O(n)。
第一次遍歷n，第二次n/2，第三次n/4，第四次n/8，第五次n/16……加起來約等于2*n，和k的值幾乎無關。
快排第一次n，第二次n，第三次n……

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62250.html

標籤：數據結構與算法

上一篇：webapi 使用swagger的如何顯示引數注釋相關問題

下一篇：Supermap的基本概念