|
【考点：数组】二维数组中的查找
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
【初始】解法一：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null) return false;
int xLen = array[0].length;
int yLen = array.length;
if(xLen == 0 || yLen == 0) return false;
for(int i = 0; i < yLen; i++) {
if(array[i][xLen - 1] < target) continue; //如果该行最大值都小于目标值，跳过查询
if(array[i][0] > target) break; //纵坐标最小值已经大于目标值，说明没有找到，结束循环
if(find(target, array[i], array[i].length - 1, 0))
return true;
else
continue;
}
return false;
}
//二分查找
public boolean find(int target, int[] array, int high, int low) {
int hi = high;
int lo = low;
if(hi < lo) return false;
int mid = (hi + lo) / 2;
if(target < array[mid]) return find(target, array, mid - 1, lo);
else if(target > array[mid]) return find(target, array, hi, mid + 1);
else return true;
}
}
分析：这个算法也就剔除了上面几行，然后开始用二分法对剩下的有可能出现值的每一行进行了查找，显得很生硬。
【改进】解法二：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null) return false;
//拿到列数
int xLen = array[0].length;
//拿到行数
int yLen = array.length;
//如果输入不合法 返回false
if(xLen == 0 || yLen == 0) return false;
//解题思路：
//1.每次选取右上角的数num = array[y][x]
//2.如果该数大于target，则当前列无效（当前列下方的元素肯定大于target） num = array[y][--x];
//3.如果该数小于target，则当前行无效（当前行左边的元素肯定小于target） num = array[++y][x];
//4.如果该数等于target，则返回，跳出循环
//初始化
int row = 0;
int column = xLen - 1; //注意： 需要xLen - 1，不然会数组越界
//标志位
boolean found = false;
while(row < yLen - 1 && column >= 0) { //注意： 需要yLen - 1，不然会数组越界
if(array[row][column] == target) {
found = true;
break;
}else if(array[row][column] > target) {
column--;
}else{
row++;
}
}
return found;
}
}
分析：逻辑条理非常清晰
更多算法解答请点击《剑指offer》66题JAVA代码算法实现全集 | 
转播
