时间复杂度为 O(m (log n + log m)) 的算法，用于在 n*m 矩阵中查找每行已排序的第 k 个最小元素？

Question

我最近遇到一个面试问题。

我们有m*n一个矩阵，每行都按非递减顺序排列（按不同元素排序）。设计一种算法，以便O(m (log m+ log n))找到k该矩阵上的第-最小元素（只有一个元素作为k第-最小元素）。

我认为这是不可能的，所以在 Google 上搜索并找到此链接和另一个解决方案以及类似问题的答案。

我认为如下：

1. 将所有行的中位数放入一个数组中，我们找到该数组的中位数O(m)并将其称为枢轴

2. 我们在 中找到该元素的排名O(m log n)。即：每一行中有多少个元素低于步骤（1）中找到的主元。

3. 通过比较k和“枢轴的排名”，我们可以知道每一行中的工作在右半部分或左半部分。（简化为m*n/2矩阵。）

但该算法的时间复杂度为O(m * log^2 n)。可以运行的算法是什么O(m (log n + log m))？有什么想法吗？

Answer 1

m - 行 n - 列

• 您是否必须需要O(m (log m+ log n))复杂的解决方案？

• 我可以想出一个O(k * log-m)具有 O(m) 额外空间的复杂解决方案

  • 对于这种复杂性，您可以使用修改后的 PriorityQueue（堆）DataStructure

  class PQObject {
      int value; // PQ sorting happens on this int..
      int m; // And m and n are positions.
      int n;
  }
  

• 您可以将第一列中的所有值放入优先级队列并开始弹出，直到第 k 个最小元素

  • 每次弹出时，请使用弹出对象中的 m 和 n 重新插入该行的下一个值。

• 最终问题归结为找到 M 个已排序数组中的第 k 个最小元素。