查找已排序行矩阵中的第 K 个最小元素

Question

这是一个面试问题。

在排序的行矩阵中找到最小的元素，但不能排序的列，并且行之间没有关系。 （第一行和第n行之间没有关系 - 所知的只是每个行都按顺序排列）

输入是这样的：

[[1,50,60],
 [20,30,40],
 [2,3,4]]
k = 5

在这种情况下，输出是

20

因为20是此矩阵中的第五小元素。

我首先想到将所有元素添加到Minheap中，然后将元素进行轮询，同时从K中减去一个元素，直到我们得到答案。我还考虑过针对O（M*N）解决方案实现QuickSelect，尽管这些解决方案并没有真正利用所有行按升序排序的事实。

解决此问题的最佳方法是什么？考虑到这一点后，我意识到这似乎是一个“合并k分类列表”的问题，在找到最小的元素后，我们在哪里停下来。

谢谢

Answer 1

假设以下情况，

[[1,3,4,...10],
[1,3,4,...10],
[1,2,4,...10]]
For k = 4, ans = 2

由于每行具有相同的开始/结束元素，并且任何两行之间没有关系，因此如果不使用一些强力强制，很难确定任何有用的信息。最简单的解决方案应该是

1. 拥有一个包含矩阵前 k 个元素的最大堆，
2. 开始遍历剩余的元素/行。如果当前元素小于 max_heap.top，则弹出堆并将当前值添加到其中。否则，停止当前行的迭代（因为这里无法获得第 k 个最小元素）

这比完整的暴力破解有一些微小的改进，但仍然有 O(m*n)< /code> 时间复杂度和 O(k) 空间复杂度。

编辑：
您可以在 O(mlog(m)) 时间内根据矩阵行的第一个元素对矩阵行进行排序（使用最后一个元素打破平局），以减少堆压入/弹出操作的数量。 （对于单调递减矩阵，您将在每种情况下推送/弹出堆元素，这会降低性能。）

Answer 2

一种确实利用排序行的方法是嵌套二分搜索，当值的范围不太大时，这种方法速度更快。如果您的矩阵有 m 行和 n 列，并且某些 Range 等于 max(Matrix)-min(Matrix)+1，时间复杂度可以写成

O(m * (log n) * (log Range))

算法背后的思想就是kth的定义> 最小元素为

• “满足k-1的值矩阵的元素小于该值。”

在矩阵中，这变成

• “矩阵每行的总和（小于该值的元素数量）等于k-1”。

在单行中，我们可以使用二分查找在 log n 时间内计算有多少元素小于某个 x。对于整个矩阵，这需要 m * log n 时间。最初，您应该扫描矩阵的第一列和最后一列，以分别查找矩阵中外部二分搜索边界的最小值和最大值。

---

这是算法其余部分的伪代码：

1. 扫描矩阵的第一列并找到最小值；调用此 low
2. 扫描矩阵的最后一列并找到最大值； 时，调用此high
3. 当low high 高：
   • 让中=（低+高）/2
   • 使用二分查找计算矩阵中小于 mid 的元素数量
     • 如果此计数小于 k-1：设置 low = mid + 1
     • 否则：设置高=中

4. 返回 low代码>

Answer 3

解决方案的关键是所有行都是分类的。我将建议以下建议：

给定一个排序的矩阵a：

1. 初始化一个最小堆，带有0 TH的TH索引值，其相应的行号为min_heap堆中的位置由值定义，并且行号用于时间优化。
2. init a index_vec = zeros（[1，n]）是lngth等于向量中所有值的行数0，因为起始索引为 0（n是行的数量）
3. 弹出min_heap的顶部，然后推入min_value_tuple
4. Advance> Advance index_vec [min_value_tuple [1]] += 1
5. push a [chosen_row，index_vec [min_value_tuple [1]]]进入min堆，作为一个带有相应行号的元重。
6. 返回步骤3。对于K times，
7. pop min_heap 的顶部

note 如果在步骤3中的循环中。到6。index_vec [ii] = m，其中m是柱状的数量，我们不会将新数字推到min_heap，而只是将堆构成以适应新的根。

时间复杂性

1. 构建初始堆需要o（n），因为在堆中
2. 将数字推入堆中的 n 数字为o（klog（n））

总运行时为o（n + klong（n））。

最坏的情况是k = m*n/2。在这种情况下，时间复杂性将为O（n + nmlog（n））= o（nmlog（n））。

空间

堆

带大小n的

需要大小n和index_vec ＆gt; n*m/2如果在翻转a的行后，矩阵中最大的数字找到了矩阵中的最大数字，则可以解决等效问题。

Answer 4

按行对矩阵进行排序，然后在行元素k times上迭代。

Time complexity: (n + k) log n
Space complexity: n * m
n = number of rows
m = number of columns

public class KthSmallestElementMatrix {

    public static void main(String[] args) throws Exception {

        int[][] matrix = {
          {1, 50, 60},
          {20, 30, 40},
          {2, 3, 4}
        };
        int k = 5;

        System.out.println(kthSmallestElement(matrix, k));
    }

    static class ArrayElement implements Comparable<ArrayElement> {

        int[] arr;

        int index;

        ArrayElement(int[] arr) {
            this.arr = arr;
            this.index = 0;
        }

        public boolean hasNext() {
            return index < arr.length;
        }

        public int next() {

            if (hasNext()) {
                return arr[index++];
            } else {
                return arr[index];
            }
        }

        @Override
        public int compareTo(ArrayElement o) {
            return Integer.compare(this.arr[index % arr.length], o.arr[o.index % arr.length]);
        }
    }

    private static int kthSmallestElement(int[][] matrix, int k) throws Exception {

        Queue<ArrayElement> q = new PriorityQueue<ArrayElement>();

        for (int i = 0; i < matrix.length; i++) {
            q.add(new ArrayElement(matrix[i]));
        }

        int element = Integer.MIN_VALUE;

        for (int i = 0; i < k; i++) {
            ArrayElement ae = q.poll();

            element = ae.next();

            if (ae.hasNext()) {
                q.add(ae);
            }
        }

        return element;
    }
}

Answer 5

让我们定义一个存储一对值的最小堆，那么该算法由以下步骤组成：

1-迭代矩阵第一列的值，并将每个值作为一对 (value, row指数）。

2-重复以下步骤k-1次：将堆顶对的行索引存储在idx中，然后删除该对。现在转到索引等于 idx 的行，并以与之前相同的方式将其中下一个未使用的元素添加到堆中。经过 k-1 次迭代后，顶部元素将包含第 K 个元素。

第一步的时间复杂度是 O(n.log n)，其中 n 是矩阵的行数。第二步的时间复杂度是 O(k.log n)，因为我们将从堆中删除/添加 k-1 个元素，并且在每个时刻堆包含不超过 n 个元素。所以总的时间复杂度是O((n+k)log n)。

Answer 6

对每行的前 k 个元素运行快速选择 O(kn) 时间。