h********e
发帖数: 1972 | 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的话，还是有机会搞出来。 |
n*s
发帖数: 752 | |
h********e
发帖数: 1972 | |
i**********e
发帖数: 1145 | 4 这题我记得有论文说 O(n) 可以解，但是算法非常复杂。
用堆 O(k log n) 就应该可以了。
请问 O(n log n) 有比 O(k log n) 快一些吗？ |
f*******n
发帖数: 12623 | 5 你弄错了什么东西。如果T(N) = O(\sqrt(N)) + T(3N/4) ，那T(N) = O(\sqrt(N))。
证明：O(\sqrt(N)) + T(3N/4) = O(\sqrt(N)) + O(\sqrt(3N/4)) = O(\sqrt(N)) ＋
\sqrt(3/4)O(\sqrt(N)) = O(\sqrt(N)) = T(N) |
h********e
发帖数: 1972 | 6 k 可以是n^2... nlogn 这里的n就是矩阵的边长。 klogn有可能比直接做还慢。。
【在 i**********e 的大作中提到】
: 这题我记得有论文说 O(n) 可以解，但是算法非常复杂。
: 用堆 O(k log n) 就应该可以了。
: 请问 O(n log n) 有比 O(k log n) 快一些吗？
|
h********e
发帖数: 1972 | 7 你再算一遍。。。
＋
【在 f*******n 的大作中提到】
: 你弄错了什么东西。如果T(N) = O(\sqrt(N)) + T(3N/4) ，那T(N) = O(\sqrt(N))。
: 证明：O(\sqrt(N)) + T(3N/4) = O(\sqrt(N)) + O(\sqrt(3N/4)) = O(\sqrt(N)) ＋
: \sqrt(3/4)O(\sqrt(N)) = O(\sqrt(N)) = T(N)
|
b******v
发帖数: 1493 | 8 T(N) = O(\sqrt(N)) + T(3N/4) =O( nlog n). N=n^2
那么T(N)=O(N^(log_4 3()=O(n^(log_2 3)) 比nlog(n)大。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 h********e 的大作中提到】
: 一般面试不会见到这种东西的。权当娱乐吧。
: 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
|
h********e
发帖数: 1972 | 9 我还是写出来吧。。。T(N) = sqrt(N) + T(3N/4) = sqrt(N) + sqrt(3N/4) + T(9N/
16) = ... = sqrt(N)+sqrt(3N/4)+sqrt(9N/16)+sqrt(3^3 N/4^3) ... = 一共重复log
_{4/3} N次。。所以最后是O(nlog n)... |
i****s
发帖数: 1152 | 10 基本上都是median of median的变种
理论上是O(N)
4
【在 h********e 的大作中提到】
: 一般面试不会见到这种东西的。权当娱乐吧。
: 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
|
f*******n
发帖数: 12623 | 11 sqrt(N)+sqrt(3N/4)+sqrt(9N/16)+sqrt(3^3 N/4^3) = sqrt(N) * (1+sqrt(3/4)+sqrt
(3/4)^2+sqrt(3/4)^3+...)
1+sqrt(3/4)+sqrt(3/4)^2+sqrt(3/4)^3+...是geometric series。一直加起来＝1/(1-
sqrt(3/4))，是一个constant。所以是sqrt(N) * O(1) = O(sqrt(N))
log
【在 h********e 的大作中提到】
: 我还是写出来吧。。。T(N) = sqrt(N) + T(3N/4) = sqrt(N) + sqrt(3N/4) + T(9N/
: 16) = ... = sqrt(N)+sqrt(3N/4)+sqrt(9N/16)+sqrt(3^3 N/4^3) ... = 一共重复log
: _{4/3} N次。。所以最后是O(nlog n)...
|
h********e
发帖数: 1972 | 12 唔那我递归方程写错了，本意是。。应该是T(N) = O(n) + T(3N/4) 不好意思。。 |
f*******n
发帖数: 12623 | 13 那T(N) = O(n)
【在 h********e 的大作中提到】
: 唔那我递归方程写错了，本意是。。应该是T(N) = O(n) + T(3N/4) 不好意思。。
|
