題目：假設序列由n個關鍵字不同的記錄構成（一個記錄有一個關鍵字），要求不經排序而從中選出關鍵字從大到小順序的前k(k<n)個記錄。試問如何進行才能使所作的關鍵字間比較次數達到最小？
有無大神會？查遍全網也沒找到相關的解釋。。。。
uj5u.com熱心網友回復：
題目描述就有問題，不經排序，選出關鍵字從大到小順序的前k……不排序選出從大到小的順序？？？按題目描述，不排序是不可能選出從大到小的，但不能n個數完全排序。
我想到的大概有3種（效率遞減）：
1.把遞回版快排修改一下，每次分組之后與k比較，只繼續遞回左或右，而不是左右都遞回（每次砍半，時間復雜度接近O(n)。找出前k個之后，給前k個區域排序。
2.主席樹。主席樹選出前k之后，與方法1一樣，區域排序
3.不完全的堆排序，建最小堆，堆排序按從大到小序排到第k就停（其實和全排序相比省不了太多時間）
uj5u.com熱心網友回復：
堆排序啊 這個就是經典的TOPN問題 建立一個大小為k的最小堆 將記錄遍歷一遍放入堆 最后剩下的就是最大的k個記錄。 java里可以用PriorityQueue來實作 參考https://my.oschina.net/leejun2005/blog/135085 里面topk的部分uj5u.com熱心網友回復：
不用排序。。直接遍歷一下所有節點，把前k大的數保留下來就行了。就跟找出最大值一個道理（用max變數存盤最大的值，遍歷所有節點，遇到比max大的就賦值進max）。。。只不過將max變數改為max陣列。uj5u.com熱心網友回復：
不排序不代表不能去比較uj5u.com熱心網友回復：
不經排序應該是說不對這包含n個關鍵字的集合排序，這樣解法就多了uj5u.com熱心網友回復：
這題無解吧，如果說時間復雜度最低應該是堆排序 O(n*lgK)但是看題目要求好像是數學意義的最少。。。。。感覺太過復雜，大概無解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/13245.html
標籤：數據結構與算法
下一篇：第一次見面