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

Question

我想知道是否有一种有效的算法来找到N×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)的时间界限.

从这里开始.