题目:二维数组中的查找
描述:在一个二维数组中,每一行都按照从左到右的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一函数,输入这样的一个二维数组,和一个数,判断数组中是否含有该整数。
思路:遍历的话能找出是否含有该整数,但是没有用到这个二维数组的一些特性,这样是不足以拿到offer的。通过题目给到的信息我们知道这个数组是从左到右递增,从上到下递增的。下面给出一个例子:
1 2 4 5
2 4 6 7
5 8 9 11
7 9 11 13
我们可以从右上角的数字开始比对,如果要查找的数字是8(输入的整数)大于选到的这个数5(也是就是右上角的数字),于是我们我们就排除了第一行,因为第一行里最大的数字都比我们要找的数字小,所以我们要找的数字肯定不在第一行里,于是我们往下挪一个,我们先到7这个数,发现还是比8小,于是我们继续往下挪,选到11,比我们要查找的8大,于是8不可能出现在11所在列了,因为再往下的数都比8大,于是我们往左挪一个,找到9,要比八大,所以就所在列可以排除,继续往左挪,就找到我们要查找的数啦。
上代码:
public static boolean findNumber(int[][] arr,int number) {
return true;
}
不好意思,搞错啦。继续上代码
public static boolean findNumber(int[][] arr,int number) {
if (arr == null) {
return false;
}
int rows = arr.length;
int columns = arr[0].length;
if (rows > 0 && columns > 0) {
int row = 0;
int column = columns - 1;
while (row < rows && column >= 0) {
if (arr[row][column] == number) {
return true;
}
// 和左上角数进行比较
else if (arr[row][column] > number) {
// 左上角数大 则往左挪挪
column -= 1;
continue;
} else {
// 左上角数小 则往右挪挪
row += 1;
continue;
}
}
}
return false;
}
总结:灵活的应用题目给的规则,使我们更容易拿到offer!