c# - 在二维排序数组中找到 k 个最小\最大的元素

Question

给定一个二维数组。行和列已排序。

以最有效的方式从二维数组中找到第 k 个最大的元素。可以就地完成吗？

Answer 1

一个稍微蛮力的就地解决方案：尝试通过二进制搜索来猜测值。你知道最大值和最小值（它们在角落里）。对于每个候选者，在遵循较小和较大元素之间的边界时计算较小元素的数量。由于数组是排序的，这个边界是一条相当短的路径穿过它。跟踪较小元素中最大值的位置。该值可能会出现多次。数一数。假设一个 NxN 数组，这将需要 O(N*B)，其中 B 是值的位数。

我只是在大声思考......我隐约记得阅读过一个令人难以置信的最佳解决方案，但我不知道在哪里。