剑指Offer:面试题3——二维数组中的查找(java实现)

问题描述:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数.

思路:取数组中的元素与目标整数比较,相等则返回true,小于则 查找当前元素的右方和下方,大于则查找当前元素的左方和上方,然而这两个区域有重叠部分,就不容易处理。

然而如果我们从数组的角落选取元素与目标整数对比,则就不会出现重叠区域了。

假如:我们从右上角选取元素,如果相等则返回true;如果大于,显然该列的元素都大于目标整数,我们就可以去掉这一列然后对比剩下的前几列;如果小于,显然该行的所有元素都小于目标整数,我们就可以去掉这一行然后对比剩下的后几行。依次类推,即可找到或找不到相应的目标整数。

/**
* 面试题3:二维数组中的查找
*/
public static boolean Find(int[][] mat, int number){
boolean found = false; if(mat != null && mat.length() > 0 && mat[0].length() > 0){
int m = mat.length();
int n = mat[0].length();
int row = 0;
int col = n-1; while(row < m && col >=0){
if(mat[row][col] == number){
found = true;
break;
}else if(mat[row][col] > number){
col--;
}else{
row++;
} } } return found;
}
上一篇:(zhuan) 126 篇殿堂级深度学习论文分类整理 从入门到应用


下一篇:ASP.NET服务器控件OnClientClick事件中Eval()作为js方法的参数的一种写法