1. 题目描述

题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数

2. 解题思路

时间复杂度是 $O(N)$,空间复杂度是$O(1)$

利用数组的排序性质:如果要查找的元素小于当前元素,那么一定不在当前元素左边的列;如果要查找的元素大于当前元素,那么一定在当前元素下面的行。

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* 题目答案
* @param {Array} arr
* @param {Number} elem
*/

function findElem(arr, elem) {
let row = arr.length - 1,
col = arr[0].length - 1
let i = 0,
j = col

while (i <= row && j >= 0) {
if (arr[i][j] === elem) {
return true
}

if (elem > arr[i][j]) {
++i
} else {
--j
}
}

return false
}

/**
* 以下是测试代码
*/

const arr = [
[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15],
]

console.log(findElem(arr, 8))
console.log(findElem(arr, 1))
console.log(findElem(arr, 145))