1 题目

leetcode 一个n*m的数组，每一行从左向右递增，每一列从上到下递增，完成一个函数，输入一个这样的二维数组和整数，判断数组中是否有含有该整数。

2 解

2.1 双重循环

二维数组只需要双重循环即可遍历，需要注意的是取二维数组的length时返回的是二维数组的行数，取二维数组中某一行的length时返回的是该行的列数，可以写出如下代码。

class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { int length=matrix.length; //两个循环 for(int i=0;i<length;i++) { int j=0; while(j<matrix[i].length) { if(matrix[i][j]>target) { //过大，跳出 break; } if(matrix[i][j]==target) { //相等 返回 return true; } //不等且小于，移动下标 j++; } } return false; } }

运行通过。

2.2 用二分替代循环

由于每一行都是有序的，所以可以使用二分查找来找到判断是否包含指定的值。

class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { int length=matrix.length; //循环+二分 for(int i=0;i<length;i++) { //二分查找 int startIndex=0; int endIndex=matrix[i].length-1; while(startIndex<=endIndex) { int middleIndex=(startIndex+endIndex)/2; //相距为1时 if(endIndex-startIndex==1) { if(matrix[i][endIndex]==target) { return true; } } if(matrix[i][middleIndex]==target) { return true; } if(matrix[i][middleIndex]>target) { //中间值大于目标值 endIndex=middleIndex-1; }else { //中间值小于目标值 startIndex=middleIndex+1; } } } return false; } }

在二分查找之前也可以对当前行进行一些判断，节省时间

if(matrix[i].length==0) continue; if( matrix[i][0]>target) { //第一个都比目标大，直接跳出。 break; } if(matrix[i][matrix[i].length-1]<target) { //最后一个都没有目标大，直接下一轮 continue; }

3 书上思路

将二维数组看作矩阵，从右上角开始查找，当目标等于当前数字时，结束查找。当目标小于当前位置的数字，则剔除当前列，当目标大于当前位置数字时，则剔除当前行。

private static boolean findNumberIn2DArray(int[][] matrix, int target) { //矩阵不为空 if(matrix==null || matrix.length==0 || matrix[0].length==0) return false; int r=0; int c=matrix[0].length-1; while(r<=matrix.length-1 && c>=0 ) { //该位置上的数与目标比较 if(matrix[r][c]==target) { //相等，返回 return true; } if(matrix[r][c]>target) { //大于，剔除列 c--; }else{ //小于，剔除行 r++; } } return false; }

全解上的实现

public boolean Find(int target, int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; int rows = matrix.length, cols = matrix[0].length; int r = 0, c = cols - 1; // 从右上角开始 while (r <= rows - 1 && c >= 0) { if (target == matrix[r][c]) return true; else if (target > matrix[r][c]) r++; else c--; } return false; }

虽然全解和我的代码有一些细微的差别， 但全都能运行。。。。。不知道是不是我理解错了。。。 主要还是边界条件需要注意，什么时候等于什么时候不等。

4 参考链接

1.官解 2.剑指 Offer 全解（Java 版）