在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { //1、暴力求解，直接遍历 /*首先判断目标矩阵是否为空：判断二维数组是否为空，要判断三种情况： 1、二维数组首地址是否为空，即array==null； 2、二维数组是否为{}，即array.length==0的情况； 3、二维数组是否为{{}}，即array.length=1&&array[0].length==0的情况； 综上所述，判断二维数组为空的条件为*/ if((matrix == null || matrix.length == 0)||(matrix.length == 1 && matrix[0].length == 0)){ return false; } //遍历数组查看是否有相等的值 //时间复杂度：O(nm)；空间复杂度：O(1)。 for(int i = 0; i < matrix.length; i++){ for(int j = 0; j < matrix[0].length; j++){ if(matrix[i][j] == target){ return true; } } } return false; //2、利用二维数组排好序的特点，从二维数组的右上角开始查找。 /*如果当前元素与目标相等，返回 true。 如果目标小于当前位置的元素，则数组中该列的元素都大于目标，向左边移动一列。 如果目标大于当前位置的元素，则数组中该行该位置向左方向的元素都小于目标，向下移动一行。*/ if((matrix == null || matrix.length == 0)||(matrix.length == 1 && matrix[0].length == 0)){ return false; } //初始化标记下标，分别记录当前的行列，从右上角开始 int row = 0;//matrix.length int col = matrix[0].length - 1; //在不越界的情况下查找 while(row < matrix.length && col >= 0){ if(matrix[row][col] == target){ return true; }else if(matrix[row][col] > target){ col --; }else{ row ++; } } return false; } }
