Leetcode（二维数组）

156 阅读 0 评论 103 点赞

我是靠谱客的博主温婉往事，这篇文章主要介绍Leetcode（二维数组），现在分享给大家，希望可以做个参考。

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如：
1,2，3,4
5,6，7,8
9.10,11,12
13,14,15,16

方法一：

相信很多同学都应该得出结论就是可以for循环，通过for循环对target数字进行对比。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

let arr = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];
function compareArr(arr, target) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (arr[i][j] == target) {
return true;
}
}
}
return false;
}
console.log(compareArr(arr, 555)); //fasle

ES6新知识用一下，其实意思是一样的

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function comapreArr(arr,target){
let arri = arr[Symble.iterator]();
for(let i of arri ){
let arrj = i[Symble.iterator]();
for(let j of arrj
){
if( j== target){
return true;
}
}
}
return false;
}

以上用js实现了一个查找，但是其时间复杂度为o(mn)=>o(n^2) 当m n趋向无穷大的时候，就是 o(n^2)
时间复杂度是很高的，如果二维数组很大，其时间复杂度会很高。

方法二：

其实通过上面的办法，咱们忽略了一个条件，就是从左到右、从上到下逐渐增大。
根据这个特性可以再往下思考，比如我先比较第一行 1,2，3,4。 target = 10；
我们直接拿末尾行的4与target进行比较，发现4<10,那么可以判断，4所属的这一行，没有符合条件的。因为4前面的值都是比4小的，更谈不上存在相等的啦。
此时这个二维数组变成：
5,6，7,8
9.10,11,12
13,14,15,16
同理比较8<target=10,故也不存在，现在二维数组变成：
9.10,11,12
13,14,15,16
再者，再拿12>target=10，说明二维数组中的行中可能存在与target相等的值。同时也可以得出12所处的这一列中，不存在与target相等的值。故现在二维数组变成：
9.10,11
13,14,15

总结：依照此规律，可以进行程序的编写，一句话是比较每行中结尾最大的数，小于目标值去掉一行，大于目标值的话，去掉一列。
methods one

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function compareArr2(arr, target) {
let rowcount = arr.length;
let columncount = arr[0].length;
let i = 0;
let j = arr[0].length - 1;
while (i < rowcount && j >= 0) {
let value = arr[i][j]
if (value == target) {
return true;
} else if (value < target) {
i += 1;
} else if (value > target) {
j -= 1;
}
}
return false;
}

methods two

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

function compareArr2(arr, target) {
let rowcount = arr[0].length;
let columncount = arr.length;
for (let i = 0; i < rowcount;) {
for (let j = columncount - 1; j > 0 && i < rowcount;) {
let value = arr[i][j];
if (value == target) {
return true;
} else if (value > target) {
j -= 1;
} else {
i += 1;
}
}
}
return false;
}
console.log(compareArr2(arr, 10));