C＃：在N×N矩陣中尋找最大m個元素的有效算法

Question

我想知道是否有一個有效的算法來找到N×N矩陣中最大的m個元素，並使用如下方法標題：

double[] greatestValues(double[][] matrix, int numberOfElements); 

任何想法？

Answer 1

如果治療的N×N矩陣爲N×N的項目的數組，你可以應用下列方法之一：

快速排序基於選擇算法快速 排序的直接應用基於事件的選擇算法可以是 用於查找k個最小或k個最大的元素 。找到k個最小元素 找到第k個最小元素，使用 中值的快速排序中值爲 算法。該 發現第k個最小元素的分區後，所有的 比第k個 更小的元素更小的元素將存在左 到第k個元素，所有元素 較大將到第k個 最小元素本右。因此，從第1個元素到第k個元素的所有 元素構成k個最小元素。時間複雜度爲 ，線性n，總數爲 元素。

基於數據結構解決方案另一種簡單的方法是將列表中的每個 元素添加到有序 集合數據結構，例如一個堆或 平衡樹， 至多k個元素。每當 數據結構有多個元素時，我們刪除最大的元素 ，這可以在O（log k） 時間內完成。每個插入操作還需要O（log k）時間，從而總體上導致O（nlog k）時間。

有可能使用改進的 廣度優先搜索算法來列表 轉變成一個堆在Θ（n）的時間，然後 橫移堆中 地方的元素在一個優先 隊列（而不是通常在BFS中使用的普通隊列 ）和 在遍歷 後終止掃描k個元素。由於隊列大小爲 在整個遍歷期間保持爲O（k），所以它將需要完成O（klogk）時間，導致該算法的時間界限爲O（n + klog k）。

從here。