经典面试题 之 在单调矩阵中查找元素

经典面试题之在单调矩阵中查找元素面试题系列经典而试题 之 单链表找环经典面试题之数组的循环右移经典面试题之洗牌问题经典面试题之在单调矩阵中查找元素经典面试题之按单词逆序经典面试题之套字典题目的大意是要

经典面试题之在单调矩阵中查找元素 面试题系列 1. 经典而试题之单链表找环 2. 经典面试题之数组的循环右移 3. 经典面试题之洗牌问题 4. 经典面试题之在单调矩阵中查找元素 5. 经典面试题之按单词逆序 6. 经典面试题之套字典 题目的大意是要求在一个N*N的矩阵中，找出一个特定的元素，这个矩阵满足两个条件：1）每一行 的元素，从左到右严格递增：2）每一列的元素，从上到下严格递增。 这道题的限制太多，以至丁•很容易想到结果。元素都是递增（或者递减也行）的，要在一行上找元 素，很显然用二分搜索了，那么一共N行，时间复杂度就是0（N*logN）.显然这不是最快的方法， 要不然题目就没有意义了。 继而想到每一行递增，每一列也递增，那么主对角线也是递增的，而且满足一个很好的性质： A16A17 AllA12A13A14A15 A26A27 A21A22A23A24A25 A36A37 A31A32A33A34A35 A46A47 A41A42/\43A44A45 A51A52A53A54 A56A57 A55 A61A62A63A64 A65A66A67 A71A72A73A74假设以上矩阵A满足递增的性质，那么对于A55而言，［AU, A75A76A77 A55］这个矩阵中所有的值都不超过 A55,而［A55,A77］这个矩阵中所有的值都不小于A55。所以说,如果要找个值比A44大，而比 A55小，那么它一定在［A15,A67］和匚A51,A76］这两个矩阵中，于是搜索规模直接减少了一