LeetCode-378 Kth Smallest Element in a Sorted Matrix

题目描述

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

题目大意

在一个整数矩阵中，按行有序排列，列有序排列，要求找出矩阵中第k小的数字。

示例

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

return 13.

解题思路

简单利用multiset就可以解决本问题，可以使用二分对每一行进行搜索以减少时间复杂度。

复杂度分析

时间复杂度：O(N² * log（N²）)

空间复杂度：O(N²)

代码

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        multiset<int> seq;
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        
        for(int i = 0; i < matrix.size(); ++i)
            for(int j = 0; j < matrix[i].size(); ++j)
                seq.insert(matrix[i][j]);
        
        auto it = seq.begin();
        for(int i = 1; i < k; ++i) {
            ++it;
        }
        return *it;
    }
};