题目链接:二维数组中的查找_牛客题霸_牛客网

描述

在一个二维数组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;}