剑指 Offer 4. 二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
答案：
1，暴力求解
当然最容易想到的是暴力求解，就是一个个查找，如果找到就返回true，没找到就返回false，代码很简单，没什么可说的。
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int rows = matrix.length, columns = matrix[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
} 2，线性查找
题中说了每行都是递增的，每列也是递增的。所以我们查找的时候可以利用这个特性，如果我们从左上角开始找，当目标值target大于当前值的时候，我们需要往更大的找，但这个时候无论往右找还是往下找都是比当前值大，所以我们无法确定该往哪个方向找。同理右下角也一样，所以我们只能从右上角或者左下角开始找。我们就用上面的数据当target等于23的时候从右上角开始找，来画个图看一下
从右上角开始找有个方便的地方就是他左边的都是比他小的，他下边的都是比他大的，如果target大于当前值我们就往下边找，如果target小于当前值我们就往左边找，来看下代码。
public boolean Find(int target, int[][] array) {
if (array == null || array.length == 0 || array[0].length == 0) {
return false;
}
int rows = array.length, col = array[0].length;
//从第0行col - 1列开始查找，也就是第1行最后一列的那个数字开始
int row = 0;
int column = col - 1;
while (row < rows && column >= 0) {
//num表示当前值
int num = array[row][column];
if (num == target) {
//如果找到直接返回
return true;
} else if (num > target) {
//到前面查找
column--;
} else {
//到下面查找
row++;
}
}
return false;
} 当然从左下角查找也是可以的，因为左下角右边的值是比他大的，上边的值是比他小的，也能区分，代码和上面差不多，来看下
public boolean Find(int target, int[][] array) {
if (array == null || array.length == 0 || array[0].length == 0) {
return false;
}
int rows = array.length, col = array[0].length;
int row = rows - 1;
int column = 0;
while (row >= 0 && column < col) {
int num = array[row][column];
if (num == target) {
//如果找到直接返回
return true;
} else if (num > target) {
//往上面找
row--;
} else {
//往右边找
column++;
}
}
return false;
} 我把部分算法题整理成了PDF文档，截止目前总共有900多页，大家可以下载阅读
链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
京公网安备 11010502036488号