【算法】二维数组中的查找

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

现有矩阵 matrix 如下：

const matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30],
];

自己实现

我唯一能想到的就是暴力破解，利用 2 个循环遍历这个二维数组，然后判断每一项是否与给定项相等，如果相等则返回 true 并终止循环。

var findNumberIn2DArray = function (matrix, target) {
  if (matrix && target) {
    for (let i = 0, len = matrix.length; i < len; i++) {
      for (let j = 0, newLen = matrix[i].length; j < newLen; j++) {
        if (matrix[i][j] === target) {
          return true;
        } else {
          return false;
        }
      }
    }
  } else {
    return false;
  }
};
// 我刚开始是上面的写法，不对，因为循环走到第一个的时候，就会返回false，中止循环，所以我修改了一下
var findNumberIn2DArray = function (matrix, target) {
  if (matrix && target) {
    for (let i = 0, len = matrix.length; i < len; i++) {
      for (let j = 0, newLen = matrix[i].length; j < newLen; j++) {
        if (matrix[i][j] === target) {
          return true;
        }
      }
    }
    return false
  } else {
    return false;
  }
};

效果如下：

image.png

以上是我的解法，思路。虽然最后可以输出正确结果，但是这样肯定还是不行的，因为没有用到题目中每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序这个条件，所以肯定不是最优解
以上算法的时间复杂度和空间复杂度分析如下:

• 时间复杂度：O(n * m)。二维数组中的每个元素都被遍历，因此时间复杂度为二维数组的大小。
• 空间复杂度：O(1)。

其他思路

const matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30],
];

方法一、线性解法

思路：
由于该二维数组是从左到右都是递增，并且从上到下也是递增，因此我们可以从第一行的最右边开始寻找，如果最右边的元素比给定的 target 大，这样就可以排除后续的所有行的数都不会等于 target，也就让列数减一，继续进行比较，知道将每一列都访问完成也找不到又或者能找到便能返回结果。同理，如果最右边的元素比给定的 target 小，则能直接排除第一行的元素，行加一继续访问判断。

var findNumberIn2DArray = function (matrix, target) {
  if (!matrix || !matrix.length || !target) return false;
  //   由于每一行的长度都相等，因此取第一行的长度即可，也就是列数
  let rows = matrix.length,
    columns = matrix[0].length;
  //   行从0开始，列从第一行最后一个元素开始
  let row = 0,
    column = columns - 1;
  //   当行小于行数，并且列数大于0时开始循环
  while (row < rows && column >= 0) {
    let item = matrix[row][column];
    //   如果两者相等，则直接返回，否则判断大小来确定是行加1还是列加1
    if (item === target) {
      return true;
    } else if (target > item) {
      row++;
    } else {
      column--;
    }
  }
  return false;
};

效果如下：

image.png

以上算法的时间复杂度和空间复杂度分析如下:

• 时间复杂度：O(n + m)。访问到的下标的行最多增加 n 次，列最多减少 m 次，因此循环体最多执行 n + m 次。
• 空间复杂度：O(1)。
  好像比我的解法用时还要多😓，但是这应该是符合面试官要求的一种解法，我自己的想法有点土，没技巧，太暴力，这个更优雅