酷应用

经典面试题：有序矩阵的快速查找

百家作者：CSDN 2021-04-08 13:17:02

【编者案】算法核心不在于框架用得有多熟练，更多在于逻辑和思维方式，很多情况都需要变换间接建模。本文将通过一个经典的面试题来描述思维过程，引导最终问题建模。

作者 | kyle? ? ? ?责编 | 欧阳姝黎

金三银四

最近招聘市场各路神仙出没，小K也打算去凑一下热闹。

热身运动，小K先和面试官过了几招，不分胜负。
接着面试官要开始放大招了。

这招怎么化解呢，等小K先思考2分钟。

分析

2.1不思考解法

从左上到右下，一个一个的对比不就行了吗，当然这肯定不是面试官期望的。

2.2逐行二分

一维的可以用二分快速查找，那就分解成一维，一行一行的用二分不就行了吗。

但每一列也是有序的，这种方法其实就没有用上这个信息了，所以肯定还有更好的方法。

找规律

一般是先想一下有没有可以套用的算法框架，如果不能发现很明显的算法，可以先分析问题的规律，然后再尝试变换间接建模。我们先尝试把所有能发现的规律都找出来。

根据问题描述，每行每列都升序。

更小规模也符合相同的规律，这就意味着可以想办法缩小问题规模。

从左上开始只能向下向右，则经过的路线升序。

从左上斜着看，还有点像小根堆。

对角线方向升序。

在对角线上选取一个数与目标数对比，可以用分治的思想，分块把大问题化解为小问题。

在边缘选取一个数，可以一行一列的删除，把大问题化解为小问题。

大于目标数，按列快速缩小问题规模。

小于目标数，按行快速缩小问题规模。

根据上面找出的规律，有很多的方式都可以缩小问题规模，那从哪个点开始判断呢。

所以从右上或者左下开始都可以。

算法建模

根据上面总结的规律，可以有很多种算法，这里以效率比较高的2种算法说明。

4.1线性缩小

代码实现

bool?solve1(vector<vector<int>>?&matrix,?ofstream?&cout,?int?x)?{
????int?i,?j;
????i?=?0;
????j?=?matrix[0].size()?-?1;
????bool?flag?=?false;
????while?(i?<?matrix[0].size()?&&?j?>=?0)?{
????????if?(matrix[i][j]?>?x)?{
????????????--j;
????????}?else?if?(matrix[i][j]?<?x)?{
????????????++i;
????????}?else?{
????????????return?true;
????????}
????}
????return?false;
}

4.2二分缩小

代码实现
按行二分，缩小列

int?searchColumn(vector<vector<int>>?&matrix,?int?up,?int?right,?int?x)?{
????int?i,?j,?mid;
????i?=?0;
????j?=?right;
????while?(i?<?j)?{
????????mid?=?(i?+?j)?/?2;
????????if?(x?<?matrix[up][mid])?{
????????????j?=?mid?-?1;
????????}?else?if?(x?>?matrix[up][mid])?{
????????????i?=?mid?+?1;
????????}?else?{
????????????i?=?j?=?mid;
????????}
????}
????if?(matrix[up][i]?>?x)?--i;
????return?i;
}

按列二分，缩小行

int?searchRow(vector<vector<int>>?&matrix,?int?up,?int?right,?int?x)?{
????int?i,?j,?mid;
????i?=?up;
????j?=?matrix.size()?-?1;
????while?(i?<?j)?{
????????mid?=?(i?+?j)?/?2;
????????if?(x?<?matrix[mid][right])?{
????????????j?=?mid?-?1;
????????}?else?if?(x?>?matrix[mid][right])?{
????????????i?=?mid?+?1;
????????}?else?{
????????????i?=?j?=?mid;
????????}
????}
????if?(matrix[i][right]?<?x)?++i;
????return?i;
}

主要过程

bool?solve2(vector<vector<int>>?&matrix,?ofstream?&cout,?int?x)?{
????int?up,?right;
????up?=?0;
????right?=?matrix[0].size()?-?1;
????while?(!(up?==?matrix.size()?||?right?<?0))?{
????????right?=?searchColumn(matrix,?up,?right,?x);
????????if?(right?<?0)?continue;
????????up?=?searchRow(matrix,?up,?right,?x);
????????if?(up?==?matrix.size())continue;
????????if?(matrix[up][right]?==?x)?{
????????????return?true;
????????}
????}
????return?false;
}

数据测试

数据生成

void?dataInit()?{
????ofstream?cout("a.in");
????int?s?=?0;
????for?(int?i?=?0;?i?<?5000;?++i)?{
????????for?(int?j?=?0;?j?<?5000;?++j)?{
????????????cout?<<?s?+?i?+?j?<<?"?";
????????}
????????s?+=?4999;
????????cout?<<?endl;
????}
}

执行效率

目标数：10002500
线性执行效率：
row=2000,?column=2500
T1=288
二分执行效率
row=2000,?column=2500
T2=10

总结

通过问题的现象，分析本质，可以发现很多隐藏的规律，然后再通过所学的知识进行问题建模，进而解决未知的问题。

2020-2021中国开发者调查报告重磅来袭，直接扫码或微信搜索「CSDN」公众号，后台回复关键词「开发者」，快速获取完整的报告内容！

?C 和 C++ 不安全？Android 支持 Rust 开发操作系统
?16岁的雅虎问答，因“不再受欢迎”将永久关闭
?滴滴、小米启动造车，特斯拉的护城河还能守多久？
?微软正式推出 OpenJDK 预览版！

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

*文章为作者独立观点，不代表爱尖刀立场

本文由 CSDN发表，转载此文章须经作者同意，并请附上出处( 爱尖刀 )及本页链接。

原文链接 https://www.ijiandao.com/2b/baijia/407342.html

图库

CSDN

关注网络尖刀微信公众号
随时掌握互联网精彩

赞助链接

百度热搜榜

排名热点搜索指数