kth kleinste Element sortierte Matrix mit QuickSelect

Question

Ich weiß, das wurde schon einmal gefragt, aber diese Frage ist über meinen spezifischen Code. Ich versuche, einen Pseudo-QuickSelect-Algorithmus zu machen, wobei ich k mit dem Mittelpunkt eines Teilintervalls einer sortierten Matrix vergleiche.

Ich bekomme immer einen Timeout-Fehler. Hier

ist die Matrix:

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

Hier ist mein Code:

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) 

I in Tupeln matrixRecur geben, die die (row, col) der Endpunkte des Intervalls enthalten. Also, wenn ich die ganze Matrix durchsuchen möchte, passiere ich (0, 0) und . matrixRecur untersucht ein Subintervall, ermittelt den Mittelpunkt anhand der Zeilenspaltennummern der Endpunkte, zählt die Anzahl der Elemente unter dem Mittelpunkt und vergleicht sie mit k. Wenn k kleiner ist als die Anzahl der Elemente unter dem Mittelpunkt (lcount), dann ist das k-kleinste Element innerhalb des linken Intervalls, da höchstens lcount Elemente weniger als der Mittelpunkt und k < lcount sind.

Ich führe dies auf einer Interview-Frage-Website und die Seite sagt mir weiterhin, dass mein Code mal ausgeht. Ich sehe nicht warum.

Answer 1

Ihre obige Vorgehensweise wird nicht funktionieren. Da Ihre Matrix reihen- und spaltenweise sortiert ist. Betrachten Sie die Matrix wie unten

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

Ihre Vorgehensweise wird in diesem Fall fehlschlagen. Sie bekommen eine Auszeit, weil Sie die gesamte 2D-Matrix durchlaufen. Die Komplexität im schlimmsten Fall wäre O(mn) (m und n sind die Anzahl der Zeilen und Spalten).

Sie können ein Min-Heap verwenden, um dieses Problem zu lösen.

Algorithmus:

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. 

Zeitkomplexität: O(n + kLogn)

Quelle: Kth smallest in 2D matrix