排序矩陣中第K個最小元素

Question

這是一個面試問題。

查找K ^th排序行和列的矩陣中的最小元素。
是否正確：K ^th最小元素是a[i, j]之一，例如i + j = K？

Answer 1

假。

考慮一個簡單的矩陣像這樣的：

1 3 5 
2 4 6 
7 8 9 

9是最大的（第9最小）元素。但是9在A [3，3]和3 + 3！= 9（不管你使用什麼索引慣例，它都不是真的）。

---

可以解決爲O這個問題（K log n）的時間通過遞增合併的行，具有堆擴充以有效地找到最小元素。

基本上，您將第一列的元素放入堆中並跟蹤它們來自的行。在每一步中，您從堆中移除最小元素，並從它所在的行中推入下一個元素（如果到達行的末尾，則不會推動任何內容）。刪除最小值並添加新元素的成本爲O（log n）。在第j個步驟中，您將刪除j th的最小元素，因此在完成k步驟後，完成操作的總成本爲O(k log n)（其中n是矩陣中的行數）。

對於上面的矩陣，您最初從堆中的1,2,7開始。您刪除1並添加3（因爲第一行是1 3 5）得到2,3,7。您刪除2並添加4以獲得3,4,7。刪除3並添加5得到4,5,7。刪除4並添加6得到5,6,7。請注意，我們正在刪除全局排序順序中的元素。你可以看到繼續這個過程將在k次迭代之後產生最小的元素。

（如果基質具有比列更多的行，然後在列進行操作，而不是減少的運行時間。）

Answer 2

O(k log(k))溶液。

• 建立一個minheap。

• 將(0,0)添加到堆中。雖然，我們還沒有找到kth最小的元素，從堆中刪除頂部元素(x,y)，並添加接下來的兩個元素[(x+1,y)和(x,y+1)]，如果它們以前沒有訪問過。

我們對大小O(k)，因此複雜的堆做O(k)操作。

Answer 3

k以n*m爲界。因此，在O(k*log(k))中運行的解決方案比O(k)更差，這實際上是O(n*m)，這是簡單的搜索。

Answer 4

似乎這只是使用該功能：每行都進行排序，但不使用其列式智能排序功能。

Answer 5

開始從左上角（0,0）遍歷矩陣，並使用二進制堆來存儲「邊界」 - 矩陣的訪問部分與其餘部分之間的邊界。

實現在Java中：

private static class Cell implements Comparable<Cell> { 

    private final int x; 
    private final int y; 
    private final int value; 

    public Cell(int x, int y, int value) { 
     this.x = x; 
     this.y = y; 
     this.value = value; 
    } 

    @Override 
    public int compareTo(Cell that) { 
     return this.value - that.value; 
    } 

} 

private static int findMin(int[][] matrix, int k) { 

    int min = matrix[0][0]; 

    PriorityQueue<Cell> frontier = new PriorityQueue<>(); 
    frontier.add(new Cell(0, 0, min)); 

    while (k > 1) { 

     Cell poll = frontier.remove(); 

     if (poll.y + 1 < matrix[poll.x].length) frontier.add(new Cell(poll.x, poll.y + 1, matrix[poll.x][poll.y + 1])); 
     if (poll.x + 1 < matrix.length) frontier.add(new Cell(poll.x + 1, poll.y, matrix[poll.x + 1][poll.y])); 

     if (poll.value > min) { 
      min = poll.value; 
      k--; 
     } 

    } 

    return min; 

} 

Answer 6

隨着人們前面提到的最簡單的方法是建立一個min heap。下面是使用的PriorityQueue Java實現：

private int kthSmallestUsingHeap(int[][] matrix, int k) { 

    int n = matrix.length; 

    // This is not necessary since this is the default Int comparator behavior 
    Comparator<Integer> comparator = new Comparator<Integer>() { 
     @Override 
     public int compare(Integer o1, Integer o2) { 
      return o1 - o2; 
     } 
    }; 

    // building a minHeap 
    PriorityQueue<Integer> pq = new PriorityQueue<>(n*n, comparator); 
    for (int i = 0; i < n; i++) { 
     for (int j = 0; j < n; j++) { 
      pq.add(matrix[i][j]); 
     } 
    } 

    int ans = -1; 
    // remove the min element k times 
    for (int i = 0; i < k; i++) { 
     ans = pq.poll(); 
    } 

    return ans; 
} 

Answer 7

//int arr[][] = {{1, 5, 10, 14}, 
//  {2, 7, 12, 16}, 
//  {4, 10, 15, 20}, 
//  {6, 13, 19, 22} 
//}; 
// O(k) Solution 
public static int myKthElement(int arr[][], int k) { 
    int lRow = 1; 
    int lCol = 0; 
    int rRow = 0; 
    int rCol = 1; 
    int count = 1; 

    int row = 0; 
    int col = 0; 

    if (k == 1) { 
     return arr[row][col]; 
    } 

    int n = arr.length; 
    if (k > n * n) { 
     return -1; 
    } 

    while (count < k) { 
     count++; 

     if (arr[lRow][lCol] < arr[rRow][rCol]) { 
      row = lRow; 
      col = lCol; 

      if (lRow < n - 1) { 
       lRow++; 
      } else { 
       if (lCol < n - 1) { 
        lCol++; 
       } 

       if (rRow < n - 1) { 
        lRow = rRow + 1; 
       } 
      } 
     } else { 
      row = rRow; 
      col = rCol; 

      if (rCol < n - 1) { 
       rCol++; 
      } else { 
       if (rRow < n - 1) { 
        rRow++; 
       } 
       if (lCol < n - 1) { 
        rCol = lCol + 1; 
       } 
      } 
     } 
    } 

    return arr[row][col]; 
}