剑指Offer:二维数组中查找

二维数组中查找

题目

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

分析

这道题主要考察我们对二维数组的应用。首先我们应该提取题中的两个关键条件:二维数组的每一行以及每一列都是递增的。最后我们需要判断该数组中是否存在一个特定的数字。
判断是否存在这个特定的数字我们只需要拿它和数组中的数字进行比较即可。我们以下面这道题为例(判断下面的二维数组中是否存在7)


1.png

我们先从左上角开始比较,1 < 7 由于二维数组的每一行以及每一列都是递增的,所以现在又有种选择一种横向查找,一种纵向查找。可以发现这种方法并没有用到题目所给出的条件,我们必须一行一行(或者一列一列)的来判断直到找到数字7(如果二维数组中没有7则二维数组中的数字都需要比较一遍)。这种方法不仅效率低而且还会造成查找区域的重叠。
现在我们换一个方向,从左下角开始比较比较,首先是6和7比较


2.png

由于6小于7,并且6处在第一列的最后一个位置(数组中的每一列都是递增的)所以第一列的数字我们可以全部排除。


3.png

接下来比较8和7


4.png

8大于7,由于数组中的每一行也是递增的,所以8后面的数字我们也可以排除。


5.png

但是8所在的这一列,我们并不能排除。所以继续向上判断


6.png

Nice,7确实存在该数组中。

通过以上分析,我们可以发现:我们从左下角开始判断,如果数组中的数字小于要查找的数字,则可以踢出这个数字所在的一整列,如果数组中的数字大于要查找的数字,则可以踢出这个数字所在的一整行。这样每判断一次都可以缩小查找的范围知道找到特定的数字或者查找范围为空。
从右上角开始也是一样的,大家可以尝试一下

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public boolean Find(int target, int [][] array) {
int len = array.length - 1;
for (int i = len; i >= 0; i --) {
for (int j = 0; j < array[i].length; j ++) {
if (target < array[i][j])
break;
else if (target == array[i][j])
return true;
}
}
return false;
}
}