题目详情:
在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
例如:
[ [1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15] ]
给定 target = 7,返回 true。
给定 target = 3,返回 false。
数据范围:矩阵的长宽满足 0≤n,m≤500 , 矩阵中的值满足0≤val≤10^9
进阶:空间复杂度 O(1) ,时间复杂度 O(n+m)
解题思路:
从二维数组的右上角开始,即初始位置为第一行的最后一列。
比较当前位置的元素与目标整数的大小关系:
如果当前元素等于目标整数,则返回 True。
如果当前元素大于目标整数,由于当前元素下方的元素一定更大,因此我们需要向左移动一列,即 col -= 1。
如果当前元素小于目标整数,由于当前元素左侧的元素一定更小,因此我们需要向下移动一行,即 row += 1。
重复步骤 2,直到找到目标整数或超出数组边界,此时返回 False。
代码实现:
function searchIn2DArray(array, target) {
if (!array || array.length === 0 || array[0].length === 0) {
return false;
}
const rows = array.length;
const cols = array[0].length;
let row = 0;
let col = cols - 1;
while (row < rows && col >= 0) {
if (array[row][col] === target) {
return true;
} else if (array[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}
// true
console.log(searchIn2DArray(
[[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15]], 7))