离职删除做的网站,网站开发好难呀,网站品牌词,西安网站建立题目描述在一个 n * m 的二维数组中#xff0c;每一行都按照从左到右递增的顺序排序#xff0c;每一列都按照从上到下递增的顺序排序。请完成一个函数#xff0c;输入这样的一个二维数组和一个整数#xff0c;判断数组中是否含有该整数。示例:现有矩阵 matrix 如下#xf…题目描述在一个 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 10000 m 1000解题思路由于每行中的数据从左到右递增每一列从上往下递减因此右上角的元素是其所在行的最大元素和所在列的最小元素同理左下角的元素是其所在列的最大元素和所在行的最小元素。直接将目标值与右上角元素或者左下角元素进行比较可以大大提高查找效率。代码bool findNumberIn2DArray(int **matrix, int matrixSize, int *matrixColSize, int target){int row 0;int col *matrixColSize - 1;if(matrix NULL || matrixSize 0 || matrixColSize 0){return false;}while((row matrixSize) (col 0)){if(matrix[row][col] target){col--;}else if(matrix[row][col] target){row;}else{return true;}}return false;}执行结果时间复杂度O(MN)空间复杂度O(1)。
