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))