QuickSelectを使用したk番目の最小要素のソート済みの行列

Question

これは前に尋ねられたことは分かっていますが、この質問は私の特定のコードに関するものです。私はソートされた行列のサブ間隔の中点にkを比較するpsuedo QuickSelectアルゴリズムを実行しようとしています。

タイムアウトエラーが発生しています。

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) 

私は間隔のエンドポイントの(row, col)を含んmatrixRecurにタプルを渡す：

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

はここに私のコードです：ここでは

は行列です。行列全体を検索したい場合は、 (0, 0)とを渡します。 matrixRecurは、サブインターバルを調べ、エンドポイントの行のcol番号に基づいて中間点を決定し、中間点よりも少ない要素の数を数え、それを kと比較します。 kが中点（ lcount）未満の要素の数よりも少ない場合は、中間点よりも多くて 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)

出典：Kth smallest in 2D matrix