在一個(gè) n * m 的二維數(shù)組中软瞎，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序拉讯。請(qǐng)完成一個(gè)高效的函數(shù)涤浇，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)魔慷。
示例:
現(xiàn)有矩陣 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蜻展。
方法一： 暴力
方法二：線性查找
由于是從左到右喉誊，從上到下遞增，所以當(dāng)訪問到一個(gè)元素時(shí)纵顾，可以排除數(shù)組中的部分元素伍茄。
從二維數(shù)組的右上角開始查找，如果當(dāng)前元素等于目標(biāo)值就返回true施逾，如果當(dāng)前元素大于目標(biāo)值幻林，就移到左邊一列，如果當(dāng)前元素小于目標(biāo)值音念，則移動(dòng)到下面一行
時(shí)間復(fù)雜度：O(n+m)
空間復(fù)雜度：O(1)
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var findNumberIn2DArray = function(matrix, target) {
let i = 0
let j = 0
if (matrix.length>0) {
j = matrix[0].length - 1
}
if ( matrix.length === 0 || matrix[0].length === 0) {
return false
}
function find (i, j) {
const temp = matrix[i][j]
if (temp === target) {
return true
} else if (target > temp) {
if (i < matrix.length - 1) {
return find(++i,j)
}
} else {
if (j > 0) {
return find(i,--j)
}
}
return false
}
return find(i, j)
};
