题目
在一个二维数组中,每一行的值都是按照从左到右递增的顺序排列,每一列都是按照从上到下递增的顺序排列 请设计一个方法,输入这样的一个二维数组和一个数字,判断这个数字是否存在于这个数组中
解决方法
方法一
遍历整个二维数组进行查找
当然,面试中只写出方法一的解法,面试官一定不会满意,所以我们得谋求另一种思路
方法二
假设有如下二维数组,我们在这个二维数组中查找是否存在 7
我们可以定义一个点,从右上角开始,循环判断该点的值与给定点值之间的关系,
如果该点的值小于给定的值,该点坐标下移一行,
小于给定点的值,坐标左移一行,
相等,返回true,循环判断直到该点的坐标越界
给定点的值为 9, 9 > 7,下一次只需要在 9 的右边查找 8 > 7,下一次在 8 的左边查找 2 < 7,下一次在 2 的下边查找 4 < 7,下一次在 4 的下边查找 7 == 7,查找成功,返回 true
方法实现
package Test;
public class Question4 {
public static void main(String[] args) {
int[][] arr =
new int[][] {
{
1,
3,
5,
7},
{
2,
4,
6,
8},
{
3,
5,
7,
9},
{
4,
6,
8,
10}
};
System.out.println(solution2(arr,
1));
}
public static boolean solution1(
int[][] arr,
int num) {
try {
for(
int i =
0; i < arr.length; i++) {
for(
int j =
0; j <arr[
0].length; j++) {
if(arr[i][j] == num) {
return true;
}
}
}
return false;
}
catch (Exception e) {
e.printStackTrace();
return false;
}
}
public static boolean solution2(
int[][] arr,
int num) {
try {
int row =
0;
int col = arr[
0].length-
1;
int std = arr[row][col];
while(row<arr.length-
1 && col>=
0) {
if(std > num) {
std = arr[row][--col];
}
else if(std < num) {
std = arr[++row][col];
}
else {
return true;
}
}
return false;
}
catch (Exception e) {
e.printStackTrace();
return false;
}
}
}