题解 | #二维数组中的查找#
二维数组中的查找
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
题目描述：
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
数据范围：矩阵的长宽满足 0≤n,m≤5000 \le n,m \le 5000≤n,m≤500 ， 矩阵中的值满足 0≤val≤1090 \le val \le 10^90≤val≤109
进阶：空间复杂度 O(1)O(1)O(1) ，时间复杂度 O(n+m)O(n+m)O(n+m)
进阶：空间复杂度 O(1)O(1)O(1) ，时间复杂度 O(n+m)O(n+m)O(n+m)
示例
输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
输入：1,[[2]]
返回值：flase
输入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：flase
代码1
function Find(target, array)
{
// write code here
let m = array.length;
if(m==0) return false;
let n = array[0].length;
if(n == 0) return false;
let i=0,j=n-1;
while(i<m&&j>=0){
if(target<array[i][j]){
j--;
}else if(target > array[i][j]){
i++;
}else{
return true
}
}
return false;
}
module.exports = {
Find : Find
};
代码2
function Find(target, array)
{
// write code here
let m = array.length;
if(m==0) return false;
let n = array[0].length;
if(n == 0) return false;
let i=m-1,j=0;
while(i>=0&&j<n){//左下角
if(target>array[i][j]){
j++;
}else if(target < array[i][j]){
i--;
}else{
return true
}
}
return false;
}
module.exports = {
Find : Find
};
思路：
假定数组为4x4矩阵，数据为
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
得矩阵图
从右上角开始 假定输入值为7
第一个对比是值为9，小于。向左移动，与8比较，小于。直到于2比较，7大于2。
由图知道同列左侧的数要小于右侧的数，上列的数要小于下列的数。故7在遇到小于7的数后的唯一选择只能是向下一列寻找。
这里可以得出一个规律，从右上角开始比较的话。假设数组为array【i】【j】(设二维数组行数为n，列数为m，则i，j初始值为0和m-1,且i<n,j>=0)
在同一列比较,i不变,
当输入值T小于array[i][j]时，向左移动，j--。
当输入值T大于array[i][j]时，向下移动，i++。
从左下角开始，逻辑相同。i的初值为n-1，j为0；
当输入值T大于array[i][j]时，向右移动，j++;
当输入值T小于array[i][j]时，向上移动，i--；
滴滴公司福利 620人发布
腾讯开放平台开奖13人在聊
