我想知道是否有一种有效的算法来查找 N x N 矩阵中最大的 m 个元素，其方法头如下所示:
double[] greatestValues(double[][] matrix, int numberOfElements);
有什么想法吗？
最佳答案
如果将 N x N 矩阵视为 N x N 项的数组，则可以应用以下技术之一:
Direct application of the quick sort based selection algorithm The quick sort based selection algorithm can be used to find k smallest or k largest elements. To find k smallest elements find the kth smallest element using the median of medians quick sort based algorithm. After the partition that finds the kth smallest element, all the elements smaller than the kth smaller element will be present left to the kth element and all element larger will be present right to the kth smallest element. Thus all elements from 1st to kth element inclusive constitute the k smallest elements. The time complexity is linear in n, the total number of elements.
Data structure based solutions Another simple method is to add each element of the list into an ordered set data structure, such as a heap or self-balancing binary search tree, with at most k elements. Whenever the data structure has more than k elements, we remove the largest element, which can be done in O(log k) time. Each insertion operation also takes O(log k) time, resulting in O(nlog k) time overall.
It is possible to transform the list into a heap in Θ(n) time, and then traverse the heap using a modified Breadth-first search algorithm that places the elements in a Priority Queue (instead of the ordinary queue that is normally used in a BFS), and terminate the scan after traversing exactly k elements. As the queue size remains O(k) throughout the traversal, it would require O(klog k) time to complete, leading to a time bound of O(n + klog k) on this algorithm.
来自here .
关于C#:在 N x N 矩阵中查找最大 m 个元素的高效算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/814186/