剑指Offer04:二维数组中的查找
题目
题目链接
题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
分析
对于这道题目,直接进行数组的遍历,复杂度太高。
于是换一种思路,首先选取数组中右上角的数字。如果该数字等于要查找的数字,则查找过程结束;如果该数字大于要查找的数字,则剔除这个数字所在的列;如果该数字小于要查找的数字,则剔除这个数字所在的行。也就是说,如果要查找的数字不咋数组的右上角,则每次都在数组的查找范围中提出一行或一列,这样每一步都可以缩小查找的范围,直到找到要要查找的数字,或者查找范围为空。

代码
此代码是从右上找:
public class Solution {
public boolean Find(int target, int[][] array) {
int rows = array.length;
if (rows == 0) {
return false;
}
int cols = array[0].length;
if (cols == 0) {
return false;
}
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0) {
if (array[row][col] < target) {
row++;
} else if (array[row][col] > target) {
col--;
} else {
return true;
}
}
return false;
}
}
从左下找思路是一样的:
public class Solution {
public boolean Find(int target, int[][] array) {
int rows = array.length;
int cols = array[0].length;
if (rows == 0 || cols == 0) {
return false;
}
int col = 0;
int row = rows - 1;
while (col < cols && row >= 0) {
if (array[row][col] < target) {
col++;
} else if (array[row][col] > target) {
row--;
} else {
return true;
}
}
return false;
}
}
Q.E.D.
Comments | 0 条评论