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

沙海
沙海
沙海
3179
文章
2
评论
2021年4月4日08:35:35杂谈 Java评论53字数 3013阅读10分2秒阅读模式
摘要

速读摘要

速读摘要文章源自JAVA秀-https://www.javaxiu.com/8895.html

算法核心不在于框架用得有多熟练，更多在于逻辑和思维方式，很多情况都需要变换间接建模。最近招聘市场各路神仙出没，小K也打算去凑一下热闹。在边缘选取一个数，可以一行一列的删除，把大问题化解为小问题。根据上面找出的规律，有很多的方式都可以缩小问题规模，那从哪个点开始判断呢。06总结通过问题的现象，分析本质，可以发现很多隐藏的规律，然后再通过所学的知识进行问题建模，进而解决未知的问题。文章源自JAVA秀-https://www.javaxiu.com/8895.html

原文约 1071 字 | 图片 23 张 | 建议阅读 3 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/8895.html

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

程序IT圈 文章源自JAVA秀-https://www.javaxiu.com/8895.html

以下文章来源于小K算法，作者kyle文章源自JAVA秀-https://www.javaxiu.com/8895.html

文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

小K算法文章源自JAVA秀-https://www.javaxiu.com/8895.html

曾就职于华为和美团，中山大学数学系本科，专注分享数学、算法、科学等硬核知识文章源自JAVA秀-https://www.javaxiu.com/8895.html

文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

点击上方蓝字 关注我，涨知识文章源自JAVA秀-https://www.javaxiu.com/8895.html

算法核心不在于框架用得有多熟练，更多在于逻辑和思维方式，很多情况都需要变换间接建模。本文将通过一个经典的面试题来描述思维过程，引导最终问题建模。文章源自JAVA秀-https://www.javaxiu.com/8895.html

01文章源自JAVA秀-https://www.javaxiu.com/8895.html

金三银四文章源自JAVA秀-https://www.javaxiu.com/8895.html

最近招聘市场各路神仙出没，小K也打算去凑一下热闹。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

热身运动，小K先和面试官过了几招，不分胜负。接着面试官要开始放大招了。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

这招怎么化解呢，等小K先思考2分钟。文章源自JAVA秀-https://www.javaxiu.com/8895.html

02文章源自JAVA秀-https://www.javaxiu.com/8895.html

分析文章源自JAVA秀-https://www.javaxiu.com/8895.html

2.1文章源自JAVA秀-https://www.javaxiu.com/8895.html

不思考解法文章源自JAVA秀-https://www.javaxiu.com/8895.html

从左上到右下，一个一个的对比不就行了吗，当然这肯定不是面试官期望的。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

2.2文章源自JAVA秀-https://www.javaxiu.com/8895.html

逐行二分文章源自JAVA秀-https://www.javaxiu.com/8895.html

一维的可以用二分快速查找，那就分解成一维，一行一行的用二分不就行了吗。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

但每一列也是有序的，这种方法其实就没有用上这个信息了，所以肯定还有更好的方法。文章源自JAVA秀-https://www.javaxiu.com/8895.html

03文章源自JAVA秀-https://www.javaxiu.com/8895.html

找规律文章源自JAVA秀-https://www.javaxiu.com/8895.html

一般是先想一下有没有可以套用的算法框架，如果不能发现很明显的算法，可以先分析问题的规律，然后再尝试变换间接建模。我们先尝试把所有能发现的规律都找出来。文章源自JAVA秀-https://www.javaxiu.com/8895.html

根据问题描述，每行每列都升序。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

更小规模也符合相同的规律，这就意味着可以想办法缩小问题规模。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

从左上开始只能向下向右，则经过的路线升序。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

从左上斜着看，还有点像小根堆。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

对角线方向升序。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

在对角线上选取一个数与目标数对比，可以用分治的思想，分块把大问题化解为小问题。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

在边缘选取一个数，可以一行一列的删除，把大问题化解为小问题。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

大于目标数，按列快速缩小问题规模。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

小于目标数，按行快速缩小问题规模。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

根据上面找出的规律，有很多的方式都可以缩小问题规模，那从哪个点开始判断呢。文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

所以从右上或者左下开始都可以。文章源自JAVA秀-https://www.javaxiu.com/8895.html

04文章源自JAVA秀-https://www.javaxiu.com/8895.html

算法建模文章源自JAVA秀-https://www.javaxiu.com/8895.html

根据上面总结的规律，可以有很多种算法，这里以效率比较高的2种算法说明。文章源自JAVA秀-https://www.javaxiu.com/8895.html

4.1文章源自JAVA秀-https://www.javaxiu.com/8895.html

线性缩小文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

代码实现文章源自JAVA秀-https://www.javaxiu.com/8895.html

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;}
文章源自JAVA秀-https://www.javaxiu.com/8895.html

4.2文章源自JAVA秀-https://www.javaxiu.com/8895.html

二分缩小文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

代码实现按行二分，缩小列文章源自JAVA秀-https://www.javaxiu.com/8895.html

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;}

按列二分，缩小行文章源自JAVA秀-https://www.javaxiu.com/8895.html

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;}

主要过程文章源自JAVA秀-https://www.javaxiu.com/8895.html

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;}
文章源自JAVA秀-https://www.javaxiu.com/8895.html

05文章源自JAVA秀-https://www.javaxiu.com/8895.html

数据测试文章源自JAVA秀-https://www.javaxiu.com/8895.html

数据生成文章源自JAVA秀-https://www.javaxiu.com/8895.html

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;    }}

执行效率文章源自JAVA秀-https://www.javaxiu.com/8895.html

目标数：10002500线性执行效率：row=2000, column=2500T1=288二分执行效率row=2000, column=2500T2=10
文章源自JAVA秀-https://www.javaxiu.com/8895.html

06文章源自JAVA秀-https://www.javaxiu.com/8895.html

总结文章源自JAVA秀-https://www.javaxiu.com/8895.html

通过问题的现象，分析本质，可以发现很多隐藏的规律，然后再通过所学的知识进行问题建模，进而解决未知的问题。文章源自JAVA秀-https://www.javaxiu.com/8895.html

如果喜欢小K的文章，请点个关注，分享给更多的人，小K将持续更新，谢谢啦!文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

关注我，涨知识文章源自JAVA秀-https://www.javaxiu.com/8895.html

经典面试题：有序矩阵的快速查找文章源自JAVA秀-https://www.javaxiu.com/8895.html

原创不易，感谢分享文章源自JAVA秀-https://www.javaxiu.com/8895.html

转发，点赞，在看！文章源自JAVA秀-https://www.javaxiu.com/8895.html

文章源自JAVA秀-https://www.javaxiu.com/8895.html

继续阅读
历史上的今天
4月
4
速蛙云 - 极致体验，强烈推荐！！！购买套餐就免费送各大视频网站会员！快速稳定、独家福利社、流媒体稳定解锁！速度快，全球上网、视频、游戏加速、独立IP均支持！基础套餐性价比很高！这里不多说，我一直正在使用，推荐购买：https://www.javaxiu.com/59919.html
weinxin
资源分享QQ群
本站是JAVA秀团队的技术分享社区, 会经常分享资源和教程; 分享的时代, 请别再沉默！
沙海
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定