当前位置: 首页 > >

从矩阵中查找数字是否存在

发布时间:

题目:一个矩阵,从左往右依次增大,从上往下依次增大;
在矩阵中查找,给定数字是否存在;


分析:从矩阵整体左往右看:在矩阵的最右边的一排,是各自一排中最大的,(灵魂画手来了)如图

右上角的第一个点(称作A点吧),有一个性质,如果比A点大,那么在第一排肯定找不到该数字的只能往下一排找;如果比A小,只能往左边移动;在移动到下一个点时,依然可以用上面的思路继续判断;
按照这个思路,最坏的结果,则是在矩阵的左下角:找到/没找到;
那么,这个算法的边界也就好确定了;


```
public boolean find(int target ,int[][] a){

int m = 0;
int n = a[0].length-1;
while(true){
if(m >a.length-1 || n <0){//边界,
return false;
}
if(target == a[m][n]){//找到了,直接返回
return true;
}

if(target < a[m][n]){//左移
n--;
continue;
}

if(target > a[m][n]){//右移
m++;
continue;
}


}





}



友情链接: