八八我家老大的朋友史# Parenting - 为人父母
a*1
1 楼
几个关于m*m matrix的问题，看看有没有更好的算法：
1. 在一个row/col sorted matrix，寻找一个数，O(m)，从最左上角开始，如果target
大，往下走；如果target小，往左走。
2. 在一个row/col sorted matrix，寻找第k大的数，我能想到的是用Young Tableau，
然后类似于Heap，每次取出最大的数，然后Heapify matrix，直到取出第K大的数。
Time complexity是 k*O(m)，O(1) space。但是这样会破坏matrix的结构。因为每次
Heapify，matrix都变动过了。有没有更好的算法？我一直想用Divide and Conquer,
取matrix中心的那个数作为pivot，然后就不知道该怎么办了。
3. 基于问题2，那如何sort entire matrix? 当然也可以用Young, Time O(m3)? 有没
有更好的办法？
4. 如果是任意一个matrix，如何sort呢？比如sort成一个：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
CLRS P.721 有一个类似的题目，哪位大侠能给个solution？为什么这样sort是正确的
？他sort出来的应该是：
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
关于matrix还会有什么引申的题目？
对了哪位大侠给讲讲KMP算法？不是很懂啊～
1. 在一个row/col sorted matrix，寻找一个数，O(m)，从最左上角开始，如果target
大，往下走；如果target小，往左走。
2. 在一个row/col sorted matrix，寻找第k大的数，我能想到的是用Young Tableau，
然后类似于Heap，每次取出最大的数，然后Heapify matrix，直到取出第K大的数。
Time complexity是 k*O(m)，O(1) space。但是这样会破坏matrix的结构。因为每次
Heapify，matrix都变动过了。有没有更好的算法？我一直想用Divide and Conquer,
取matrix中心的那个数作为pivot，然后就不知道该怎么办了。
3. 基于问题2，那如何sort entire matrix? 当然也可以用Young, Time O(m3)? 有没
有更好的办法？
4. 如果是任意一个matrix，如何sort呢？比如sort成一个：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
CLRS P.721 有一个类似的题目，哪位大侠能给个solution？为什么这样sort是正确的
？他sort出来的应该是：
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
关于matrix还会有什么引申的题目？
对了哪位大侠给讲讲KMP算法？不是很懂啊～
