首页 > 代码库 > Search a 2D Matrix
Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3, return true.
Hide Tags
Array Binary Search思路：
从右上角开始，如果等于，则返回TRUE，如果大于二维数组的数字，列--，否则行++;算法和测试用例如下：
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
bool isFound = false;
int rows = matrix.size();
cout << rows << endl;
int columns = matrix.front().size();
cout << columns << endl;
if (rows>0&&columns>0)
{
int row = 0;
int column = columns - 1;
while (row < rows && column >= 0)
{
if (matrix[row][column] == target)
{
isFound = true;
break;
}
else if (matrix[row][column] > target)
{
--column;
}
else
{
++row;
}
}
}
return isFound;
}
};
void main()
{
vector<vector<int> > matrix{ { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, {6,8,11,15} };
Solution s;
bool isFound = s.searchMatrix(matrix, 121);
cout << isFound << endl;
system("pause");
}注意获取行和列的方式。
Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。