【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素

作者推荐

视频算法专题

本文涉及的基础知识点

二分查找算法合集

LeetCode378. 有序矩阵中第 K 小的元素

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
示例 1：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
示例 2：
输入：matrix = [[-5]], k = 1
输出：-5
提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
1 <= k <= n2

二分查找

Cnt(x)函数，计算小于等于x的个数。如果Cnt(x)小于k，则x一定不是第k小的元素。Cnt(x) >= k，且x最小。由于是找第一个符合的，故用左开右闭空间。

Cnt(x)

容易想到的方法是：各行分别二分查找，时间复杂度是: O(nlogn)。
时间复杂度O(n)的做法是：
对倒数第一行暴力查找，使得mat[0][0,…r) 全部小于等于x，mat[0][r]不存在或大于x。
从r开始，对倒数第二行到倒数第n行分别暴力查找。
由于r不复位，所以r最多从0到n，故时间复杂度是O(n)，不是O(n2)。

代码

class Solution {
public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
		m_c = matrix.size();
		int left = matrix.front().front()-1, r = matrix.back().back();
		while (r - left > 1)
		{
			const auto mid = left + (r - left) / 2;
			if (Cnt(matrix, mid) >= k)
			{
				r = mid;
			}
			else
			{
				left = mid;
			}
		}
		return r;
	}
	int Cnt(const vector<vector<int>>& matrix, int x)
	{
		int iCnt = 0;
		for (int r = m_c - 1,right=0; r >= 0; r--)
		{
			for (; (right < m_c) && (matrix[r][right] <= x); right++);
			iCnt += right;
		}
		return iCnt;
	}
	int m_c;
};

# 测试用例

```cpp
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	vector<vector<int>> matrix;
	int k;
	{
		Solution slu;
		matrix = { {1,5,9},{10,11,13},{12,13,15} }, k = 8;
		auto res = slu.kthSmallest(matrix, k);
		Assert(13, res);
	}
	{
		Solution slu;
		matrix = { {-5} }, k = 1;
		auto res = slu.kthSmallest(matrix, k);
		Assert(-5, res);
	}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

1