速读摘要文章源自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
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

评论