C＃：在N×N矩阵中找到最大m个元素的高效算法

Question

我想知道是否有一种有效的算法可以在N x N矩阵中找到最大的m个元素，方法标题如下：

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

有什么想法吗？

Answer 1

如果将N x N矩阵视为N x N项的数组，则可以应用以下技术之一：

  

直接应用基于快速排序的选择算法快速   基于排序的选择算法可以   用来找k最小或k最大   元素。找到k个最小的元素   找到第k个最小的元素   中位数的中位数快速排序   算法。分区之后   全部找到第k个最小元素   小于第k个的元素   左边会出现较小的元素   到第k个元素和所有元素   更大的将出现在   第k个最小的元素。所以   元素从第1个元素到第k个元素   包容性构成k最小   元素。时间的复杂性是   n中的线性，总数   元件。

     

基于数据结构的解决方案另一个简单的方法是添加每个解决方案   列表的元素成为有序的   设置数据结构，例如堆或   自平衡二叉搜索树，   最多k个元素。每当   数据结构超过k   元素，我们删除最大的   元素，可以在O（log k）中完成   时间。每次插入操作也   需要O（log k）时间，导致   整个O（nlog k）时间。

     

可以转换列表   在（＆n）时间内进入堆中，然后进入堆中   使用修改后的遍历堆   广度优先搜索算法   将元素放在优先级中   队列（而不是普通队列   通常用于BFS），和   遍历后终止扫描   恰好是k个元素。作为队列大小   在整个遍历中仍然是O（k），   它需要O（klog k）时间   完成，导致时间限制   该算法的O（n + klog k）。

从此处。