使用QuickSelect的K个最小元素排序矩阵

Question

我知道以前有人问过这个问题，但这个问题是关于我的具体代码。我试图做一个psuedo-QuickSelect算法，将k与排序矩阵子区间的中点进行比较。

我一直收到一个超时错误。

以下是矩阵：

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8

下面是我的代码：

def kthSmallest(self, matrix, k):
    """
    :type matrix: List[List[int]]
    :type k: int
    :rtype: int
    """

    return self.matrixRecur(matrix, (0, 0), (len(matrix) - 1, len(matrix[0]) - 1), k)

def matrixRecur(self, splicedMatrix, left, right, k):
    start_row, start_col = left
    end_row, end_col = right
    mid_row = (start_row + end_row)/2
    mid_col = (start_col + end_col)/2

    i = start_row
    j = start_col
    lcount = 0
    while(not (i == mid_row and j == mid_col)):
        if j < len(splicedMatrix[0]):
            j += 1
        else:
            j = 0
            i += 1
        lcount += 1
    if k == lcount:
       return splicedMatrix[mid_row][mid_col]
    elif k < lcount:
        return self.matrixRecur(splicedMatrix, (start_row, start_col), (mid_row, mid_col), k)
    else:
        return self.matrixRecur(splicedMatrix, (mid_row, mid_col + 1), (end_row, end_col), k-lcount)

我将元组传递给matrixRecur，其中包含区间的endpoint的（row， coll）。因此，如果我想搜索整个矩阵，我会传递（0,0）和（n， n）。matrixRecur将查看子区间，根据endpoint的行号确定中点，计算小于中点的元素数量，将其与k进行比较。如果k小于小于中点的元素数（lCount），那么第k个最小的元素在左间隔内，因为最多有lCount小于中点的元素和k

我在一个面试问题网站上运行这个，网站继续告诉我我的代码超时了。我不明白为什么。

Answer 1

你的上述方法行不通。因为矩阵是按行和列排序的。考虑下面的矩阵

10, 20, 30, 40
15, 25, 35, 45
24, 29, 37, 48
32, 33, 39, 50

在这种情况下，你的方法将失败。因为要遍历整个2D矩阵，所以需要暂停。最坏情况下的时间复杂度是O（mn）（m和n分别是行数和列数）。

您可以使用最小堆来解决这个问题。

算法：

1. Build a min heap of first row elements. A heap entry also stores row number and column number.

2. for(int i=0;i<k;i++)
       Get minimum element (or root) from min heap.
       Find row number and column number of the minimum element.
       Replace root with the next element from same column and min-heapify the root.

3. Return the last extracted root.

时间复杂度：O（n kLogn）

来源：二维矩阵中的第k个最小值