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。