Stanford 的 Monte Winslow# Biology - 生物学
h*e
1 楼
一般面试不会见到这种东西的。权当娱乐吧。
P1:两个sorted数组，每个数组选一个数，相加。求第k大的和。
P2:一个n*n的矩阵，行和列都是sorted的，求第k大数。假设是从左到右递增，从上到
下递增。
P1是P2的特例。
这个题目O(n^2)是最直接的解法。然后有个O(k logn)的用堆来做，稍微tricky一些。
下面说下n logn的怎么搞出来。
首先想到的是套median的算法。比如一开始拿矩阵中心的那个数,say q 出来。从右上
开始往左下 能用O(n)的时间找出一条分界线, 这条分界线是单调的。使得这条线以上
的数比q小，下的数比q大。然后扔掉不对的那一半递归。第一次这么扔能扔掉至少1/4
的矩阵。问题来了，第二次继续在剩下的里面怎么做。
剩下的是神马。。是n 个row。每个row大小都不一样。目标是在这堆row里面扔掉至少1
/4. 这时候，每个row 可以找出一个median来。然后一般的做法找medians的median。
但是在这里行不通，因为有的row size比较小，这么做不能保证每次扔掉1/4. 必须修
正算法。要找weighted median。这个weight就是row size。这个weighted median 在
线性时间很容易搞，标准算法。可以用反证法很容易证明如果用weighted median 那么
在所有的row 中间至少有1/4的数比他大，1/4的数比他小。 这样就能保证每次扔掉1/4
. 扔的时候，也只要线性时间完成，因为又是一遍从右上到左下的查找。
最后的时间是：T(N) = O(\sqrt(N)) + T(3N/4) =O( nlog n). N=n^2.
这题还有个O(n)时间的解法。。没事就别去想了。。。这个nlogn的算法，如果熟悉
median的话，还是有机会搞出来。
P1:两个sorted数组，每个数组选一个数，相加。求第k大的和。
P2:一个n*n的矩阵，行和列都是sorted的，求第k大数。假设是从左到右递增，从上到
下递增。
P1是P2的特例。
这个题目O(n^2)是最直接的解法。然后有个O(k logn)的用堆来做，稍微tricky一些。
下面说下n logn的怎么搞出来。
首先想到的是套median的算法。比如一开始拿矩阵中心的那个数,say q 出来。从右上
开始往左下 能用O(n)的时间找出一条分界线, 这条分界线是单调的。使得这条线以上
的数比q小，下的数比q大。然后扔掉不对的那一半递归。第一次这么扔能扔掉至少1/4
的矩阵。问题来了，第二次继续在剩下的里面怎么做。
剩下的是神马。。是n 个row。每个row大小都不一样。目标是在这堆row里面扔掉至少1
/4. 这时候，每个row 可以找出一个median来。然后一般的做法找medians的median。
但是在这里行不通，因为有的row size比较小，这么做不能保证每次扔掉1/4. 必须修
正算法。要找weighted median。这个weight就是row size。这个weighted median 在
线性时间很容易搞，标准算法。可以用反证法很容易证明如果用weighted median 那么
在所有的row 中间至少有1/4的数比他大，1/4的数比他小。 这样就能保证每次扔掉1/4
. 扔的时候，也只要线性时间完成，因为又是一遍从右上到左下的查找。
最后的时间是：T(N) = O(\sqrt(N)) + T(3N/4) =O( nlog n). N=n^2.
这题还有个O(n)时间的解法。。没事就别去想了。。。这个nlogn的算法，如果熟悉
median的话，还是有机会搞出来。
