题目:
在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下:
限制:
0 <= n <= 1000
0 <= m <= 1000
本题与:力扣240(java&python)-搜索二维矩阵 II(中等)相同
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
方法一:暴力求解,直接遍历二维数组中的每个元素,并与target相比较。
1 class Solution { 2 public boolean findNumberIn2DArray(int[][] matrix, int target) { 3 //判空 4 if (matrix.length == 0 || matrix[0].length == 0) return false; 5 int n = matrix.length; 6 int m = matrix[0].length; 7 //直接遍历每个元素 8 for (int[] rows : matrix){ 9 //遍历每一行中的每个元素 10 for (int num : rows){ 11 if (num == target) return true; 12 } 13 } 14 return false; 15 } 16 }
方法二:坐标轴法:参考k神的题解,每次排除一行
在当前索引不越界的情况下:从矩阵 matrix 左下角元素(索引设为 (i, j) )开始遍历,并与目标值对比:
①当 matrix[i][j] > target 时,那么[i,j]右边的所有元素都大于目标值,执行 i-- ,即消去第 i 行后面的所有元素;
②当 matrix[i][j] < target 时,那么[i,j]上面的所有元素都小于目标值,执行 j++ ,即消去第 j 列上面的所有元素;
③当 matrix[i][j] = target 时,返回true。
当行索引或列索引越界时,则代表矩阵中无目标值,返回 false 。
1 class Solution { 2 public boolean findNumberIn2DArray(int[][] matrix, int target) { 3 //判空 4 if (matrix.length == 0 || matrix[0].length == 0) return false; 5 //n:行;m:列 6 int n = matrix.length, m = matrix[0].length; 7 int i = n - 1, j = 0; 8 while (i >= 0 && j < m){ 9 if (matrix[i][j] > target){ 10 i--; 11 }else if (matrix[i][j] < target){ 12 j++; 13 }else { 14 return true; 15 } 16 } 17 return false; 18 } 19 }标签:Java,matrix,int,offer04,length,查找,return,false,target From: https://www.cnblogs.com/liu-myu/p/17261133.html