【算法刷题第一题】牛客题:二维数组中的查找

二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)

题目大纲

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递 增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解决思路

解决思路:
1.查找的过程,本质是排除的过程
一次排除一个和一次排除一批肯定是排除一批的效率更高.

观察数组会发现:
x可以通过比较二维数组右上角的值或者左下角的值来一排一排的进行排除
左下角的值和右上角的值都有一个特点
分别是这一列最大的,这一行最小的,
这一行最大的,这一列最小的.

我们在比较的时候可以直接拿着这个目标值和右上角或者左下角的值进行比较,这里好比和右上角的值作比较.

如果当前的值x比右上角的值要小,那么就说明当前你要查找的值x是绝对不会出现在右上角值这一列中的.
这样就可以把整体的这一列排除

剩下的就是这一部分内容:

它还是一个二维矩阵,还可以采用类似的做法进行排除.
如果当前的值x比右上角的值要大,那么就说明当前你要查找的值x是绝对不会出现在右上角值这一行中的.

这样这一行我们就排除了 

剩下的还是一个二维矩阵.

2.临界条件

①找到了,比较两个数是否先相同,相同退出.

②没找到,行或者列出现了越界的情况,不满足条件,程序退出 

代码实现

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null){
            return false;
        }
        int i = 0;
        int j = array[0].length - 1;
        while(i < array.length && j >= 0){
            if(target > array[i][j]){
                i++;
            }else if(target < array[i][j]){
                j--;
            }else{
                return true;
            }
        }
        return false;
 
    }
}