leetcode378.有序矩阵中第K小的元素（中等）_leetcode 378. 有序矩阵中第 k 小的元素 python 时间复杂度

n^2约等于10的5次方，写成n。
解法一：排序。 时间复杂度O(nlogn)

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        
        vector<int> nums;
        for (auto& row : matrix) {
            for (auto& each : row) {
                nums.push_back(each);
            }
        }
        sort(nums.begin(), nums.end());
        return nums[k - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解法二：优先队列（大顶堆）。 时间复杂度O(nlogn)

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        
        priority_queue<int> pq;
        for (auto& row : matrix) {
            for (auto& each : row) {
                if (pq.size() < k) pq.push(each);
                else if (each < pq.top()) {
                    pq.pop();
                    pq.push(each);
                } 
            }
        }
        return pq.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解法三：多路归并 （利用了行递增的特点）时间复杂度O(nlogn)。
具体：用优先队列保存每一行的最小值，如果该元素所在位置后面还有元素就把下一个元素放到堆中。top出k-1次后top即需要的值。
易错点：维护的是一个小顶堆而不是大顶堆

class Solution {
public:
    struct cmp {
        bool operator()(vector<int>& v1, vector<int>& v2) const{
            return v1[0] > v2[0]; //'>'表示小顶堆
        }
    };
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        
        vector<int> elem;
        priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
        int n = matrix.size();
        for (int i = 0; i < n ;++i) {
            pq.push(vector<int>{matrix[i][0], i, 0});
        }
        for (int i = 0; i < k - 1; ++i) {
            auto tp = pq.top();
            pq.pop();
            if (tp[2] < n - 1) {
                pq.push(vector<int>{matrix[tp[1]][tp[2] + 1], tp[1], tp[2] + 1});
            }
        }
        return pq.top()[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

解法四：二分查找（同时利用行 列均递增的特点）时间复杂度O(nlog(r-l)) 最优！！！
细节：将矩阵分成两部分，左边所有的元素均小于等于mid，统计出左半部分元素的个数cnt，也就是找出一个最小的mid值，满足cnt >= k

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        
        int n = matrix.size();
        int l = matrix[0][0] - 1, r = matrix[n - 1][n - 1] + 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            int cnt = 0; 
            int j = 0;
            for (int i = 0; i < n; ++i) {
                if (i == 0) { //i == 0时用二分
                    j = upper_bound(matrix[0].begin(),matrix[0].end(),mid)-matrix[0].begin();
                }else { //i > 0时j向左移动
                    while (j - 1 >= 0 && matrix[i][j - 1] > mid) --j;
                }
                if (j == 0) break;
                cnt += j;
            }
            if (cnt >= k) r = mid;
            else l = mid;     
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25