LeetCode - HelloWorld开发者社区

一目录

不折腾的前端，和咸鱼有什么区别

一目录

二题目

三解题思路

四统计分析

五解题套路

二题目

在一个 n * m 的二维数组中：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。示例:现有矩阵 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 = 5，返回 true。给定 target = 20，返回 false。限制：0 <= n <= 10000 <= m <= 1000注意：本题与主站 240 题相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */var findNumberIn2DArray = function(matrix, target) {};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三解题思路

拿到题目，惯例分析：

暴力破解：二次循环遍历，查找到值
暴力优化：设置中断条件
字符串查找
【X】区间判断：先横排，再纵排，二分查找

半个钟后出来的结果不是很乐观，第 4 种方法没有很好地想出来，但是第 4 种应该是最优化的。

最后参考了下题解，优化成：

暴力破解：二次循环遍历，查找到值
暴力优化：设置中断条件
字符串查找
【X】区间判断：先横排，再纵排，二分查找
利用题意：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。参考：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-zuo/

OK，下面一一讲解我的思路技巧：

1、暴力破解：二次循环遍历，查找到值

var findNumberIn2DArray = function(matrix, target) {  for (let i = 0; i < matrix.length; i++) {    for (let j = 0; j < matrix[i].length; j++) {      if (matrix[i][j] === target) {        return true;      }    }  }  return false;};

这个是最容易想到的了，懂得 for 输出九九乘法表的，这个应该都能写出来。

2、暴力优化：设置中断条件

var findNumberIn2DArray = function(matrix, target) {  for (let i = 0; i < matrix.length; i++) {    for (let j = 0; j < matrix[i].length; j++) {      if (matrix[i][j] === target) {        return true;      }      if (matrix[i][j] > target) {        break;      }    }  }  return false;};

在上面的代码中，我们傻乎乎地进行了暴力破解，一行一行查找，那么有没有法子更快呢？

有！当我们遍历每一行的时候，如果该行的其中某个元素大于 target 之后，我们就不需要判断后面的数字了，因为题目表明：每一行是递增的，每一列也是递增的。

仔细想了一下，它比不上最优解，是因为它的起手位置不对，详细可以看后面

3、字符串查找

var findNumberIn2DArray = function(matrix, target) {  let matrixStr = '';  for (let i = 0; i < matrix.length; i++) {    matrixStr += `#${matrix[i].join('#')}#`;  }  if (matrixStr.includes(`#${target}#`)) {    return true;  }  return false;};

这种方法应该属于 奇技淫巧 了，怎么说？

因为我将整个二维数组换成一个字符串，然后判断字符串是否包含某元素。

虽然看似只有 for()，其实应该是 for() + join()，跟暴力破解一样的傻憨憨。

4、题解区

var findNumberIn2DArray = function(matrix, target) {  let i = matrix.length - 1, j = 0;  while (i >= 0 && j < matrix[0].length) {    if (matrix[i][j] > target) {      i -= 1;    } else if (matrix[i][j] < target) {      j += 1;    } else {      return true;    }  }  return false;};

这种方法看到后很容易理解，但是如果是自己写的话可能不太容易想到。

这里从表格的左下角开始，逐步向右上角查找：

列1

列2

列3

列4

列5

行1

行2

行3

行4

行5

假设我们需要查找 8，从行5列1 开始：

行5列1：开头 18 大于 8，排除这一行（ i -= 1）
行4列1：开头 10 大于 8，排除这一行（ i -= 1）
行3列1：开头 3 小于 8，干掉这一列（ j += 1）
行3列2：开头 6 小于 8，干掉这一列（ j += 1）
行3列3：开头 9 大于 8，干掉这一行（ i -= 1）
行2列3：开头 8，返回 true

这就是这种解法的好处。

这时候，我们回到解法 2 中 jsliang 说的那句话：

仔细想了一下，它比不上最优解，是因为它的起手位置不对，详细可以看后面

为什么会有这句话呢？

我们可以先看一份代码，数据证明优先：

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],];console.time('暴力优化');var findNumberIn2DArray1 = function(matrix, target) {  for (let i = 0; i < matrix.length; i++) {    for (let j = 0; j < matrix[i].length; j++) {      if (matrix[i][j] === target) {        return true;      }      if (matrix[i][j] > target) {        break;      }    }  }  return false;};findNumberIn2DArray1(matrix, 30);console.timeEnd('暴力优化');console.time('题解区');var findNumberIn2DArray2 = function(matrix, target) {  let i = matrix.length - 1, j = 0;  while (i >= 0 && j < matrix[0].length) {    if (matrix[i][j] > target) {      i -= 1;    } else if (matrix[i][j] < target) {      j += 1;    } else {      return true;    }  }  return false;};findNumberIn2DArray2(matrix, 15);console.timeEnd('题解区');

输出结果（5 次）：

暴力优化: 0.317ms题解区: 0.138ms暴力优化: 0.193ms题解区: 0.070ms暴力优化: 0.194ms题解区: 0.088ms暴力优化: 0.193ms题解区: 0.069ms暴力优化: 0.192ms题解区: 0.070ms

可以看到的的确确是比我们的暴力优化快，原因在哪？

对于表格：

列1

列2

列3

列4

列5

行1

行2

行3

行4

行5

暴力优化查找，从左上角到右下角，需要 25 次（整个表）
题解区查找，从左下角到右上角，需要 9 次（18 -> 10 -> 13 -> 14 -> 17 -> 16 -> 12 -> 11 -> 15）

虽然都是中断，但是起手位置决定了你需要走的次数，分析出这次的内容，甘拜下风！

四统计分析

这四种解法在 LeetCode 的统计如下：

解法

执行用时 / 击败率

内存消耗 / 击败率

解法 1

84 ms / 27.85%

37.4 MB / 100.00%

解法 2

72 ms / 70.33%

37.4 MB / 100.00%

解法 3

92 ms / 19.02%

43.8 MB / 100.00%

解法 4

60 ms / 97.63%

36.3 MB / 100.00%

其实不看也一样，上面已经分析得明明白白了。

五套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

如果小伙伴有更好的思路想法，或者没看懂其中某种解法，欢迎评论留言或者私聊 jsliang~

不折腾的前端，和咸鱼有什么区别！

LeetCode

jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。

浪子神剑 会每天更新面试题，以面试题为驱动来带动大家学习，坚持每天学习与思考，每天进步一点！

扫描上方二维码，关注 jsliang 的公众号（左）和 浪子神剑 的公众号（右），让我们一起折腾！

jsliang 的文档库由梁峻荣采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。