0%

[Leetcode]378. Kth Smallest Element in a Sorted Matrix(C++)

题目描述

题目链接: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 the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth 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 值小,可以收缩右边界;反之则收缩左边界。代码如下:

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
#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