C++版 - 剑指offer 面试题3：二维数组(矩阵)中数的查找(leetcode 74. Search a 2D Matrix) 题解
C++版 - 剑指offer 面试题3：二维数组(矩阵)中数的查找(leetcode 74. Search a 2D Matrix) 题解
剑指offer 面试题 二维数组中的查找
提交网址： http://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154
参与人数：11920 时间限制：1秒 空间限制：32768K 本题知识点：查找
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
输入描述:
array： 待查找的二维数组 target：查找的数字
输出描述:
查找到返回true，查找不到返回false
分析：
如果矩阵右上角的值比target大，删除所在的列，列号-1，在剩下的元素中继续找；如果矩阵右上角的值不大于target，删除所在的行，行号+1，在剩下的元素中继续找，找到相等的元素就退出.
由于在线oj给的C++版输入是向量，故不能直接使用C语言风格的二维数组展开为一维的方法。
AC代码:
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool Find(vector<vector<int> > array, int target) {
int rows=array.size(); // 行数
int cols=array[0].size(); // 列数
int i=0, j=cols-1;
bool found = false;
while(j>=0 && j<cols && i<rows) // i>=0 默认满足，无须再判断
{
if(array[i][j] == target) { found = true; break; }
else if(array[i][j] > target) j--; // 如果矩阵右上角的值比target大，删除所在的列，列号-1
else i++; // 如果矩阵右上角的值不大于target，删除所在的行，行号+1
}
return found;
}
};
// 以下为测试部分
/*
int main()
{
Solution sol;
int i,j;
vector<vector<int> > arr(5, vector<int>(3));
for (i = 0; i < arr.size(); i++)
for (j = 0; j < arr[0].size(); j++)
arr[i][j] = 2*i*j;
cout<<sol.Find(arr,4)<<endl;
vector<vector<int> > 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}
};
int target = 30;
cout<<sol.Find(matrix,target)<<endl;
return 0;
}
*/leetcode 74. Search a 2D Matrix
Total Accepted: 79103 Total Submissions: 233263 Difficulty: Medium
提交网址： https://leetcode.com/problems/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.
Leetcode AC代码：
#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows=matrix.size(); // 行数
int cols=matrix[0].size(); // 列数
int i=0, j=cols-1;
bool found = false;
while(j>=0 && j<cols && i<rows) // i>=0 默认满足，无须再判断
{
if(matrix[i][j] == target) { found = true; break; }
else if(matrix[i][j] > target) j--; // 如果矩阵右上角的值比target大，删除所在的列，列号-1
else i++; // 如果矩阵右上角的值不大于target，删除所在的行，行号+1
}
return found;
}
};
int main()
{
Solution sol;
vector<vector<int>> vec1={{1}};
vector<vector<int>> vec2=
{
{1, 3, 5, 7},
{10, 11, 16, 20},
{23, 30, 34, 50}
};
int res1 = sol.searchMatrix(vec1, 2);
int res2 = sol.searchMatrix(vec2, 3);
printf("%d\n", res1);
printf("%d\n", res2);
return 0;
}