百度PHP实习一面面试题－算法－二维有序矩阵的查找
时间：2015-01-11 17:39:59
收藏：0
阅读：332
题目描述
有一个二维矩阵，每一行的元素，从左到右保持严格递增，每一列的元素，从上到下保持严格递增。查找给定元素elem，返回NULL或元素位置。
| 1 | 3 | 7 | 15 | 16 |
| 2 | 5 | 8 | 17 | 19 |
| 3 | 6 | 9 | 18 | 20 |
| 7 | 18 | 20 | 22 | 24 |
| 9 | 23 | 24 | 28 | 33 |
思路
先从对角线进行一次鉴定，左上角为矩阵最小值，右下角为最大值，不在区间内，说明查找的值不在矩阵内，否则：
从左下角开始找，如果当前元素大于elem，则向上走；否则向右走。复杂度O(M+N)。
原文：http://www.cnblogs.com/asplamapie/p/4216727.html
评论（0）