题目描述
题目链接:378. Kth Smallest Element in a Sorted Matrix
Given an
n x n
matrix
where each of the rows and columns are sorted in ascending order, return thekth
smallest element in the matrix.Note that it is the
kth
smallest element in the sorted order, not thekth
distinct element.
例子
例子 1
Input:
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output:13
Explanation: The elements in the matrix are[1,5,9,10,11,12,13,13,15]
, and the 8th smallest number is 13
例子 2
Input:
matrix = [[-5]], k = 1
Output:-5
Constraints
n == matrix.length
n == matrix[i].length
1 <= n <= 300
-10^9 <= matrix[i][j] <= -10^9
- All the rows and columns of
matrix
are guaranteed to be sorted in non-degreasing order.1 <= k <= n^2
解题思路
由于每一行都是有序的,所以我们用数组最小和最大值作为边界,可以在每一行通过二分查找找到小于中间值的元素个数,如果该数量比 k
值小,可以收缩右边界;反之则收缩左边界。代码如下:
#include <algorithm>
#include <vector>
class Solution {
public:
int kthSmallest(std::vector<std::vector<int>>& matrix, int k) {
int n = matrix.size();
int left = matrix[0][0];
int right = matrix[n - 1][n - 1];
while (left < right) {
int mid = (left + right) / 2;
int count = 0;
for (int i = 0; i < matrix.size(); ++i) {
count +=
std::upper_bound(matrix[i].begin(), matrix[i].end(), mid) -
matrix[i].begin();
}
if (count < k)
left = mid + 1;
else
right = mid;
}
return left;
}
- 时间复杂度:
O(n log n log(MAX-MIN))
- 空间复杂度:
O(1)
GitHub 代码同步地址: 378.KthSmallestElementInASortedMatrix.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions