题目链接:二维数组中的查找_牛客题霸_牛客网
描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
数据范围：矩阵的长宽满足 0 \le n,m \le 5000≤n,m≤500 ， 矩阵中的值满足 0 \le val \le 10^90≤val≤109
进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m)
示例1
输入：
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：
true
说明：
存在7，返回true
第一种方法:暴力解题法
思路
遍历整个二维数组,找到返回true,否则返回false
public 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,没有就返回false
public int searchsecond(int[] array,int target){int left=0;int right = array.length-1;while(left <= right){int mid = (right-left)/2 + left;if(target < array[mid]){right = mid-1;}else if(target > array[mid]){left = mid+1;}if(target == array[mid]){return 1;}}return -1;}public boolean Find (int target, int[][] array) {for(int i = 0 ; i < array.length ; i++){int is = searchsecond(array[i],target);if(is > 0){return true;}}return false;}第三种方法:Z字查找法
思路
从左下或者右上这两个角出发,
因为对于左下角而言:行是增,列是减
对于右上角而言:行是减,列是增
这样我们就可以通过大小来控制遍历数组,如果找到返回true,没有就返回false
public boolean Find (int target, int[][] array) {int line = array.length-1;int row = 0;while(line >= 0 && row <= array[0].length-1){int index = array[line][row];if(index < target){row++;}else if(index > target){line--;}if(index == target){return true;}}return false;}本文链接：https://my.lmcjl.com/post/13975.html
展开阅读全文
4 评论