知名的定制网站建设提供商,网站做建筑三维图,郑州住房和城乡建设局网站,石家庄最新消息发布题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例
输入#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18…题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
示例
输入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根据每行都是递增的这个原则这一行的元素都会小于target则抛弃这行元素。若右上角的元素大于target根据每列都是递增的这个原则这一列的元素都会大于target则抛弃这列元素。 不断循环直到找到目标值为止
func searchMatrix(matrix [][]int, target int) bool {m : len(matrix)n : len(matrix[0])i, j : 0, n-1 // 从右上角开始for i m-1 j 0 { // 还有剩余元素if matrix[i][j] target {return true}if matrix[i][j] target {i} else {j--}}return false
}
