使用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