使用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其含有间隔的端点的(row, col)。所以，如果我想搜索整个矩阵，我通过(0, 0)和。 matrixRecur将查看子区间，根据端点的行列数确定中点，对小于中点的元素数进行计数，并将其与k进行比较。如果k小于中点（lcount）以下的元素的数量，则第k个最小元素在左侧区间内，因为最多有lcount个元素小于中点，并且。

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

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)

来源：Kth smallest in 2D matrix