剑指offer__4__二维数组中的查找
题目：二维数组中的查找
描述：在一个二维数组中，每一行都按照从左到右的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一函数，输入这样的一个二维数组，和一个数，判断数组中是否含有该整数。
思路：遍历的话能找出是否含有该整数，但是没有用到这个二维数组的一些特性，这样是不足以拿到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！
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-08-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读