搜索二维矩阵

难度:简单

描述:

写出一个高效的算法来搜索 m × n 矩阵中的值。

这个矩阵具有以下特性:

  1. 每行中的整数从左到右是从小到大排序的。
  2. 每行的第一个数大于上一行的最后一个整数。

样例:

[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
1
2
3
4
5

给出 target = 3,返回 true

题目分析:

双循环找出是否有这个值,根据第二个特性,我们可以跳过一些第二层循环,算法更具效率。

代码:

/**
 * @param matrix: matrix, a list of lists of integers
 * @param target: An integer
 * @return: a boolean, indicate whether matrix contains target
 */
const searchMatrix = function(matrix, target) {
  for (let key of matrix.keys()) { // 遍历外层数组
    let value = matrix[key]; // 拿到每行元素
    // 判断target是否在当前行中,跳过其他不必要循环
    if (target <= value[value.length - 1]) { 
      for (let item of value.keys()) { // 遍历行中元素 
        if (target === value[item]) { // 找到值
          return true;
        } else if (target < value[item]) {  // 值超过target即找不到(因为是排序的)
          return false;
        }
      }
    }
  }
  return false;  // 没有找到即返回false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Last Updated: 9/23/2018, 4:55:09 PM