[剑指Offer]5.二维数组中的查找

题目

在一个二维数组中,每一行都依照从左到右递增的顺序排序,每一列都依照从上到下递增的顺序排序。请完毕一个函数,输入这种一个二维数组和一个整数。推断数组中是否含有该整数。

思路

[算法系列之三十三]杨氏矩阵

代码

/*---------------------------------------
* 日期:2015-07-19
* 作者:SJF0115
* 题目: 5.二维数组中的查找
* 网址:http://www.nowcoder.com/books/coding-interviews/abc3fe2ce8e146608e868a70efebf62e?rp=1
* 结果:AC
* 来源:剑指Offer
* 博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std; class Solution {
public:
bool Find(vector<vector<int> > array,int target) {
int row = array.size();
if(row == 0){
return false;
}//if
int col = array[0].size();
if(col == 0){
return false;
}//if
int i = 0,j = col - 1;
while(i < row && j >= 0){
// 大于目标 剔除这个数字所在的列
if(array[i][j] > target){
--j;
}//if
// 小于目标 剔除这个数字所在的行
else if(array[i][j] < target){
++i;
}//else
else{
return true;
}//else
}//while
return false;
}
}; int main(){
Solution s;
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<<s.Find(matrix,target)<<endl;
return 0;
}
上一篇:flask实践--自动化平台搭建


下一篇:2018.6.20 Java考试试题总结(Java语言基础与面向对象编程)最新版