题目
编写一个高效的算法来搜索 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++**实现。
