【二分查找】【z型搜索】LeetCode240:搜索二维矩阵

发布时间:2023年12月18日

LeetCoe240搜索矩阵

本文涉及的基础知识点

二分查找算法合集

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1:

在这里插入图片描述

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true
示例 2:
在这里插入图片描述
输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false
参数范围:
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

二分查找

按行或列二分查找。时间复杂度:O(mlogn)。

class Solution {
public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		for (const auto& v : matrix)
		{
			auto it = std::equal_range(v.begin(), v.end(),target);
			if (it.second > it.first)
			{
				return true;
			}
		}
		return false;
	}
};

测试用例

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

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]);
	}
}

int main()
{
	vector<vector<int>> matrix;
	int target;
	{
		Solution slu;
		matrix = { {1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30} };
		target = 5;
		auto res = slu.searchMatrix(matrix, target);
		Assert(true, res);
	}
	{
		Solution slu;
		matrix = { {1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30} };
		target = 20;
		auto res = slu.searchMatrix(matrix, target);
		Assert(false, res);
	}

	//CConsole::Out(res);
}

Z字形查找

时间复杂度:O(n+m)。
令r=0,c=m_c-1。比较mat[r][c]和目标数。
大于目标数 删除此列c–
小于目标数 删除此行r++
等于目标数 找到,返回true。
退出循环条件:行数[r,m_c)为0或列数(-1,r]为0。退出时,说明没找到。

class Solution {
public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		m_r = matrix.size();
		m_c = matrix.front().size();
		for (int r = 0, c = m_c - 1; (r < m_r) && (c >= 0);)
		{
			const int iCmp = matrix[r][c] - target;
			if (0 == iCmp )
			{
				return true;
			}
			else if (iCmp > 0)
			{
				c--;
			}
			else
			{
				r++;
			}
		}
		return false;
	}
	int m_r, m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

文章来源:https://blog.csdn.net/he_zhidan/article/details/135043731
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。