题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
思路
- 通过每一行从左到右都是递增的,每一列从上到下也是递增的,可以去通过比较数字大小,来删除某一列或者某一个行。
- 将二维数组想象成矩阵。从数组的右上角数字 m 开始。
- 如果 m == target,那么说明数组中含有该整数,直接返回 true。
- 如果不相等,那么继续比较。
- 如果 m > target 成立,那么根据题意,m 所在那一列的所有数字都是比 target 大的,那么可以去除该列,然后继续取右上角的数字为 m。
- 如果 m < target 成立,那么根据题意,m 所在哪一行的所有数字都是比 target 小的,那么可以去除该行,然后继续取右上角的数字为 m。
- 去反复判断,直至所有的数字都不等于 target,那么返回 false。
代码
public class Solution {
public boolean Find(int target, int [][] array) {
if (array == null || array.length <= 0 || array[0].length <= 0) {
return false;
}
// 获取行数
int rows = array.length;
// 获取列数
int cols = array[0].length;
// 右上角数字的索引
int row = 0;
int col = cols - 1;
// 只要没查找完,就继续判断
while (row < rows && col >= 0) {
if (array[row][col] == target) {
return true;
} else if (array[row][col] > target) {
// 去除该列
col--;
} else {
// 去除该行
row++;
}
}
return false;
}
}