题目链接

牛客在线oj题——二维数组中的查找

题目描述

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

[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7，返回 true。
给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n, m≤500 0≤n,m≤500 ， 矩阵中的值满足 0≤val≤10 ^ 9 0≤val≤10 ^ 9

进阶：空间复杂度 O(1)，时间复杂度 O(n+m)

题目示例

示例1:

输入：
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：
true

说明：
存在7，返回true

示例2:

输入：
1,[[2]]

返回值：
false

示例3

输入：
3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：
false

说明：
不存在3，返回false

解题思路

查找一个元素最省力的方式就是暴力搜索，但是这种方式太粗暴，我们应该根据题目给出的条件来找到合理的搜索方法。根据条件，排除的元素越多，证明搜索的方法越牛逼

题目给出条件——每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。因此如果当前位置的元素大于目标值，那么和当前位置同一列的，位于当前元素下面的元素都可以排除

同样的，如果当前位置的元素小于目标值，那么和当前位置同一行的，位于当前元素左面的元素都可以排除

因此，我们只需要从数组的右上角开始和目标值比较，如果小于目标值就往下走，如果大于目标值就向左走。
如果走出了数组的边界，证明该数组中没有这个元素

完整代码

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]){j--;} else if (target > array[i][j]){i++;} else {return true;}}return false;}
}