题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
题目分析：
解法1：
因为有序，所以可以直接双重for循环，对目标值和数组值进行判断，最好情况迭代一次，最坏情况迭代 mn 次 ，时间复杂度O(mn) ，空间复杂度 O(1)
解法2：
因为有序，所以可以个一维数组采用二分查找法，时间复杂度降低到 O(log),空间复杂度是O(1)
代码实现
public class _01_Find2DArray {
public static void main(String[] args) {
int[][] array = {{1, 2, 3}, {2, 3, 4}, {3, 4, 7}};
int target = 7;
System.out.println(find(target, array));
System.out.println(findBinarySearch(target, array));
}
public static boolean findBinarySearch(int target, int[][] array) {
int res = 0;
for (int i = 0; i < array.length; i++) {
res = Arrays.binarySearch(array[i], target);
if (res >= 0 && res < array[0].length) {
break;
}
}
if (res < 0 || res > array[0].length) {
return false;
} else {
return true;
}
}
public static boolean find(int target, int[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if (array[i][j] == target) {
return true;
}
}
}
return false;
}
}
测试
true
true
