长春企业网站模板建站,为企网站,wordpress主题定制器,c2c网址有哪些在一个 n * m 的二维数组中#xff0c;每一行都按照从左到右递增的顺序排序#xff0c;每一列都按照从上到下递增的顺序排序。请完成一个高效的函数#xff0c;输入这样的一个二维数组和一个整数#xff0c;判断数组中是否含有该整数。 示例:
现有矩阵 matrix 如下#x…在一个 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 来源力扣LeetCode 链接https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 解题报告
这题很容易想到的就是二分了nlogm级别的做法。
但是这题其实还有更优解。毕竟谁说只能从头开始遍历了呢
抓住这题的特性我们每一次判断其实就可以排除一些元素。
如果a[i][j]target则它下边和右边的元素必定被排除。
如果a[i][j]target则它左边和上边的元素必定被排除。
发现如果从右上角开始往左下角走则必定会路过要找的元素。
AC代码
func findNumberIn2DArray(matrix [][]int, target int) bool {n : len(matrix)if(n 0) {return false;}m : len(matrix[0])i, j : 0, m-1for in j0 {if matrix[i][j] target {j--} else if(matrix[i][j] target) {i} else {return true}}return false
} 如果题目改一下成这样
编写一个高效的算法来判断 m x n 矩阵中是否存在一个目标值。该矩阵具有如下特性
每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。则可以通过引入中间层的方法来解决。
即二分的时候抽象成一个一维数组来屏蔽掉底层二维数组的结构。
