杨氏矩阵算法和思维

这里就不介绍什么是杨氏矩阵了，直接给出一个杨氏矩阵查找算法的例子，然后反思下自己的思维能力，也总结提高下自己的分析能力，希望可以从今天这个简单的问题上学到更多。

 

引子：之前算法期末考试出过一个题目，有一个矩阵类似下面这个样子，行从左到右越来越小，列从上到下越来越大，让你找一个元素x,如何在O（n)时间内找到，n表示行列个数总和，如下，找9

10 6 4 2 0

12 7 6 3 1

13 8 7 5 2

这种情况下，可以从左上角开始比较，如果比x大，那么第一列都得去除，变成

6 4 2 0

7 6 3 1

8 7 5 2

接着从左上角比较，如果小，就把第一行去除，

7 6 3 1

8 7 5 2

再比较，比9小，去除第一行

8 7 5 2

再比较去除8，去除7，5，2

这样的话每次去除最多一行或者一列，时间复杂性是O(m+n)。

 

杨氏矩阵

接着同学问了个杨氏矩阵的问题，如下矩阵，如何查找9

 1  3  4  5  7 10
 2  4  7 12 13 15
 4  5  8 13 14 16
 6  8 10 15 17 19
 8 10 12 16 18 21
11 12 15 19 20 22

这个时候，傻了，发现恩，跟刚才的不一样，这下是分布不对，就直接说不会。。。。。。

 

回过头来再看看，不就是把上边的矩阵来个置换吗，怎么就不会了呢？

 

思维

这次是碰巧想到吗，怎么逆转都想不到，要如何避免，如何锻炼呢？？？

 

有时候应该尝试着把题目问题距离形象化处理，注意观察，换种思路。