1. 题目描述

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

2. 解题思路

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

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

3. 代码

/**
 * 题目答案
 * @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));
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