在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
之前一直都很傻,想得过于繁琐,将矩阵分成三部分来求解:
看了剑指offer之后恍然大悟,膜拜大神中。。。小虫子还需要继续加油啊:
剑指offer中的大体思路是:
对矩阵从最右上的元素开始比较:
1.如果cur>target,则将cur所在列从查找范围中删除
2.如果cur<target,则将cur所在行从查找范围中删除
3.如果cur==target,则找了了目标数
贴上剑指offer 中的例子帮助理解(喜欢图,喜欢图,不喜欢文字,就贴图好了):
代码实现:
public class Solution { public boolean Find(int target, int [][] array) { int rows=array.length; int cols=array[0].length; for(int i=0;i<rows;i++){ for(int j=cols-1;j>=0;j--){ if(array[i][j]==target){ return true; }else if(array[i][j]>target){ continue; }else{ break; } } } return false; } }