经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 职业生涯 » 查看文章
前端常见算法面试题之 - 二维数组中的查找[JavaScript解法]
来源:cnblogs  作者:吴潇雄  时间:2018/10/31 8:48:58  对本文有异议

--------------------- 
作者:吴潇雄 
来源:CSDN 
原文:https://blog.csdn.net/weixin_43439741/article/details/83511843 
版权声明:本文为博主原创文章,转载请附上博文链接!

--------------------- 

题目描述

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

输入输出分析
每当拿到一个算法题的时候,不要脑子中稍微有点思路后,就开始写代码。而是先把题目中规定的参数搞清楚,然后把参数的例子写出来。

本题两个参数举例:

递增二维数组
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15

注意 题目只说每一行是递增的,没有说增幅是多少,不要以为增幅是1。同时也没有说行数和列数相等

要查找的整数
比如:7、5、0、16

对应的输出结果:true、false、false、false

实现思路
暴力遍历法
面试官要的肯定不是这个结果,直接跳过

二分查找法
仔细看这个二维数组最右上角这个数。它所在的行,左面的数字比它小;所在的列,下面的数字比它大:

 

如果要查询的数字比9大,那么9所在的行就不用在比较了,接下来只需要比较9下面的所有行

 

如果要查询的数字比9小,那么9所在的列就不用在比较了,接下来只需要比较9左面的所有列

 

通过这一次的比较,我们就能得到一个新的范围(矩形)。接着继续利用新范围右上角的数字,与要查找的整数进行比较。比较过后,又能得到一个新的进一步缩小的范围(矩形)。如此往复,直到找到目标整数,或者没有找到。

每一次比较的过程,比较类似二分查找

 

每一步都是通过比较所在行左面数字和所在列下面数字的大小,确定下一步指针的移动方向。

同理,我们还可以从矩形的左下角的数字开始比较

最后,别忘了要把特殊情况考虑进去,比如参数的特殊值

代码实现
function find(target, array) {
let rows = 0; // 右上角数字所在的行
let cols = array[0].length - 1; // 右上角数字所在的列
let result = false;

// 特殊情况判断. 其他特殊情况比如target不在array里,这里不在列举
if(array.length === 0) return false;

while(cols >= 0 && rows < array.length) {
if(array[rows][cols] === target) {
result = true;
break;
} else if(array[rows][cols] > target) {
// 如果右上角数字比目标数字大,向左移动指针
cols--;
} else {
// 如果右上角数字比目标数字小,向下移动指针
rows++;
}
}

return result;
}

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号