c# - C#：在 N x 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)。

从这里。