LeetCode

Stella981
• 阅读 576

一 目录

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

目录

一 目录

二 题目

三 解题思路

四 统计分析

五 解题套路

二 题目

在一个 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) {};

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

三 解题思路

拿到题目,惯例分析:

  1. 暴力破解:二次循环遍历,查找到值

  2. 暴力优化:设置中断条件

  3. 字符串查找

  4. 【X】区间判断:先横排,再纵排,二分查找

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

最后参考了下题解,优化成:

  1. 暴力破解:二次循环遍历,查找到值

  2. 暴力优化:设置中断条件

  3. 字符串查找

  4. 【X】区间判断:先横排,再纵排,二分查找

  5. 利用题意:每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。参考: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

1

4

7

11

15

行2

2

5

8

12

19

行3

3

6

9

16

22

行4

10

13

14

17

24

行5

18

21

23

26

30

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

  1. 行5列1:开头 18 大于 8,排除这一行( i -= 1

  2. 行4列1:开头 10 大于 8,排除这一行( i -= 1

  3. 行3列1:开头 3 小于 8,干掉这一列( j += 1

  4. 行3列2:开头 6 小于 8,干掉这一列( j += 1

  5. 行3列3:开头 9 大于 8,干掉这一行( i -= 1

  6. 行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

1

4

7

11

15

行2

2

5

8

12

19

行3

3

6

9

16

22

行4

10

13

14

17

24

行5

18

21

23

26

30

  • 暴力优化查找,从左上角到右下角,需要 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 的公众号(左)和 浪子神剑 的公众号(右),让我们一起折腾!

LeetCode

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

本文分享自微信公众号 - 飘飞的心灵(gh_e57c56f669b2)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
2年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
2年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Stella981 Stella981
2年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这