首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

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

  • 25-02-22 08:41
  • 2572
  • 10376
blog.csdn.net

作者推荐

视频算法专题

本文涉及的基础知识点

二分查找算法合集

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

378有序矩阵中第 K 小的元素

二分查找

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
文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览58836 人正在系统学习中
群中有博文配套源码
QQ群名片
注:本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/136434982"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top