二维数组中的查找

1. 题目描述

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

2. 解题思路

时间复杂度是，空间复杂度是

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

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. 代码