我有一个2D数组(实际上是一个图像)大小为N x N，我需要找到数组中M个最大值的下标(M <<N * N)。线性化索引或二维坐标都很好。数组必须保持完整(因为它是一个图像)。我可以临时复制一份，但是对数组进行排序会打乱索引。
我可以在数组上做一个完整的传递(即。O(N²)也可以。谁有一个好的算法来尽可能高效地做到这一点?
选择是排序的简单姊妹(连续重复十次)。选择算法不如排序算法为人所知，但仍然很有用。
你不能做得比O(N^2) (in N)更好，因为没有任何迹象表明你不能访问数组的每个元素。
一个好的方法是保持一个由M个最大元素组成的优先级队列。这就得到了O(N x N x log M)
遍历数组，在遍历过程中排队对(元素、索引)。队列中的元素按第一个组件排序。
一旦队列有M个元素，现在就不需要排队了:
- 查询队列最小元素
- 如果数组的当前元素较大，则将其插入队列并丢弃队列中最小的元素
如果M较大，则优先对数组进行排序。
注意: @Andy Finkenstadt提出了一个很好的观点(在你的问题的评论中):你绝对应该在"数据位置的方向"遍历你的数组:确保你连续读取内存。
同样，这是可并行化的，唯一不可并行化的部分是在加入子进程时合并队列。
您可以将数组复制到元组(value，原始X，原始Y)的一维数组中，并在(O(n)时间内从中构建一个基本堆，前提是您将堆实现为数组。
您可以在O(M lg n)时间内检索M个最大的元组，并从元组中引用它们的原始x和y。
如果你要复制输入数组来进行排序，这比线性遍历整个数组来挑选数字要糟糕得多。
问题是M有多大?如果它很小，你可以将结果(即具有2D索引和值的结构体)存储在一个简单的数组或向量中。这样可以最大限度地减少堆操作，但当你找到一个比你的向量更大的值时，你就必须把它移过来。
如果你期望M变得非常大，那么你可能需要一个更好的数据结构，比如二叉树(std::set)或使用有序的std::deque。Std::set会减少元素在内存中移动的次数，而如果你使用Std::deque，它会做一些移动，但它会显著减少你必须去堆的次数，这可能会给你更好的性能。
你的问题没有以任何有趣的方式使用二维，在二维数组中考虑等效问题更容易。
有两种主要的方法来解决这个问题:
-
维护一个包含M个最大元素的集合，并遍历数组。(使用堆可以让你更有效地做到这一点)。
这很简单，在您的情况下可能更好(M <<N)
-
使用选择，(以下算法是快速排序的改编):
- 创建一个辅助数组，包含索引[1..N]。
- 选择任意索引(及对应的值)，对索引数组进行分区，较小的元素对应的索引往左，较大的元素对应的索引往右。
- 重复这个过程，二进制搜索风格，直到缩小M个最大的元素。
这对于大m的情况很好。如果你想避免最坏的情况(与快速排序相同)，那么看看更高级的算法，(如中位数选择的中位数)
从数组中搜索最大值的次数是多少?如果你只搜索一次，那么只扫描它，保留M个最大的。
如果您多次这样做，只需将值插入排序列表(可能最好实现为平衡树)。