1.定义：
（此定义摘自：http://blog.csdn.net/dqjyong/article/details/7648698）
杨氏矩阵数据结构的特点有（如下图）：
（1）是一个M*N矩阵，并且对于同一行左边的元素要小于（或大于）右边的元素，同一列上面的元素要小于（或大于）下面的元素；
（2）如过元素不够组成一个M*N矩阵，即矩阵有一定的空余空间，那么可以采用+∞（递减的情况为-∞）填充。
2.查找图示
此题目曾经被搜狗的某面试官问过，（网上某人居然也说被问过，难道搜狗的题库这么小。。。）当时我答的是二分查找，每次去掉1/4，最后他看不下去了，好像忍受了我很久的样子，说这个方法太慢了，查了一下网上对其复杂度的介绍：该算法的递归式为f(mn)=3f(mn/4)+O(1)，根据主定理知，时间复杂度为：O((mn)^(log4(3)))（未经证实。。。）然后告诉我了一种每次可以去掉一行或者一列的方式，也就是下面这张图显示的方法，比如寻找12这个数字，从右上角（或者左下角）开始找，如果当前值比12小则去掉当前行，不用再找了，直接进入下一行，如果当前值比12大则去掉当前列，也就是说直接左移，不会再找当前列的其他值了。两幅图分别代表从右上角和左下角开始查找的情况
Read full article from 杨氏矩阵【上】 - Tristan's blog
No comments:
Post a Comment