编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -104 <= matrix[i][j], target <= 104
javascript 暴力解法
/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix = function(matrix, target) { for(let i=0;i<matrix.length;i++){ for(let j=0;j<matrix[0].length;j++){ if(matrix[i][j]===target){ return true } } } return false };
javascript 数组查找
/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ /* 以二维数组左下角为原点，建立直角坐标轴。 若当前数字大于了查找数，查找往上移一位。 若当前数字小于了查找数，查找往右移一位。 */ var searchMatrix = function(matrix, target) { let x = matrix.length-1,y = 0 while(x>=0 && y<matrix[0].length){ if(matrix[x][y]===target){ return true }else if(matrix[x][y]>target){ x-- }else{ y++ } } return false };
javascript 二分法
/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix = function(matrix, target) { let m = matrix.length,n=matrix[0].length let low = 0,high = m*n-1 while(low<=high){ let mid = Math.floor((high-low)/2)+low //中位 let x = matrix[Math.floor(mid/n)][mid%n] //所在的值 if(x<target){ low = mid+1 }else if(x>target){ high = mid-1 }else{ return true } } return false };
Typescript 以上两种也可以改为ts
function searchMatrix(matrix: number[][], target: number): boolean { let x: number = matrix.length - 1, y:number = 0 while (x >= 0 && y < matrix[0].length) { if (matrix[x][y] === target) { return true } else if (matrix[x][y] > target) { x-- } else { y++ } } return false };
python 暴力解法
class Solution(object): def searchMatrix(self, matrix, target): for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j]==target: return True return False
python any函数
any() 函数用于判断给定的可迭代参数 iterable 是否全部为 False，则返回 False，如果有一个为 True，则返回 True。元素除了是 0、空、FALSE 外都算 TRUE。
语法
def any(iterable): for element in iterable: if element: return True return False
解法
class Solution(object): def searchMatrix(self, matrix, target): return any(target in row for row in matrix)
Go 数组查找
func searchMatrix(matrix [][]int, target int) bool { m := len(matrix) n := len(matrix[0]) var i = 0 for i < m && n > 0 { if target == matrix[i][n-1] { return true } else if target < matrix[i][n-1] { n-- } else { i++ } } return false }
