查找 2D 排序数组中最小最大的元素
本文关键字：元素 2D 排序 数组 查找 | 更新日期: 2023-09-27 17:57:12
给定一个二维数组。对行和列进行排序。
以最有效的方式从二维数组中找到第 k 个最大的元素。可以就地完成吗？
一个稍微暴力的就地解决方案：尝试通过二叉搜索来猜测值。您知道最大值和最小值（它们在角落）。对于每个候选项，在遵循较小元素和较大元素之间的边界时，计算较小的元素数。由于数组是排序的，因此此边界是穿过它的相当短的路径。跟踪较小元素中最大值的位置。此值可能会多次出现。数一数。假设一个 NxN 数组，这将采用 O（N*B），其中 B 是值的位数。
我只是在大声思考...我依稀记得读到过一个令人难以置信的最佳解决方案，但我不知道在哪里。