求排序矩阵中_present_的第K个最小元素

Question

我的问题是受到这个特殊的SO评论的启发，这个评论没有得到回答（我自己也面临这个问题）：

我试图找到排序矩阵中第K个最小的元素：

给定一个nxn矩阵，其中每个行和列都按升序排序，返回矩阵中第k个最小的元素
请注意，它是排序顺序中的第k个最小元素，而不是第k个独立元素

输入：矩阵=[[1,5,9]，[10,11,13]，[12,13,15]，[12,13,15]，k=8
输出：13
说明：矩阵中的元素是[1,5,9,10,11,12,13,13,15]，第8个最小的数字是13

我的代码是这样的：

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int lowest=INT_MAX, highest=INT_MIN;
        for(vector<int> row: matrix) {
            lowest=min(lowest, row[0]);
            highest=max(highest, row[row.size()-1]);
        }
        
        while(lowest<highest) {
            int mid=lowest+(highest-lowest+1)/2;
            int places=0;
            
            for(int i=0; i<matrix.size(); i++) {
                places+=(upper_bound(matrix[i].begin(), matrix[i].end(), mid)-matrix[i].begin());
            }
            if(places<=k) lowest=mid;      //this gives a number _not_ in the matrix (14)
            else highest=mid-1;
            // if(places<k) lowest=mid+1;  //this gives a number _in_ the matrix (13)
            // else highest=mid;   //also use mid=lowest+(highest-lowest)/2 instead;
        }
        
        return lowest;
    }
};

注释代码返回矩阵中存在的数字（13），而未注释代码返回矩阵中不存在的14。

有什么好处？找到矩阵中的数字背后的直觉是什么？这里是ideone的工作代码。

Answer 1

让我给出另一种解决这个问题的方法，因为行和列是按升序排序的，对于矩阵中位于（x，y）位置的每个元素elem，如果它们是有效索引，那么位于（x1，y）的元素和元素（x1，y1）都小于elem。

然后我们确定矩阵中的最小元素是矩阵[0][0]，如果我们去掉这个元素，最小的元素就是矩阵[0][1]和矩阵[1][0]之间的最小元素。如果我们不停地移除元素，情况就会如此。

我们的算法将把每个候选元素放在一个最小的堆（优先级队列）中，这些元素在某个时候是矩阵中剩余的最小元素（我们不会直接修改矩阵），首先堆将只包含（0,0）处的元素，并且它在矩阵中索引，这样我们就可以快速定位它，表示为对

我们的步骤如下，弹出堆中最小的元素，将两个新的候选元素放入堆中最小，并重复直到弹出k元素。

您可能已经注意到，我们的堆中会有重复的数字，因为一个数字可以由堆顶部的元素和堆左侧的元素插入堆中，我们不希望这样，所以让我们来解决这个问题。

现在，只有当我们弹出的元素在第一行时，我们才会得到右边的元素。如果我们这样做，堆中就不会有任何重复的索引，但是，这能工作吗？，这个问题的答案是肯定的，因为列和行是有序的，所以我们不可能得到一个最小值，而不得到它上面和它左边的所有元素，我们仍然在确保至少有一种方法可以按升序到达每个元素。

您还应该注意到，我们最多在堆中插入2*k个元素。

实现细节：我假设矩阵中至少有k个元素。

typedef pair<int, int> pii;
typedef pair<int, pair<int, int>> matrixValue;

int kthSmallest(vector<vector<int>>& matrix, int k) {
    priority_queue<matrixValue, vector<matrixValue>, greater<>> priorityQueue;

    matrixValue smallest = matrixValue(matrix[0][0], pii(0, 0));

    priorityQueue.push(smallest);

    for (int i = 1; i < k; ++i) {
        matrixValue iterSmallest = priorityQueue.top();
        priorityQueue.pop();

        int x = iterSmallest.second.first;
        int y = iterSmallest.second.second;

        if ( x == 0 and y + 1 < matrix[0].size() ) {
            priorityQueue.push(matrixValue(matrix[x][y + 1], pii(x, y + 1)));
        }
        if ( x + 1 < matrix.size() ) {
            priorityQueue.push(matrixValue(matrix[x + 1][y], pii(x + 1, y)));
        }
    }

    return priorityQueue.top().first;
}