哥独自悲伤去了# Joke - 肚皮舞运动
f*e
1 楼
We have a N X N matrix whose rows and columns are in sorted order. How
effeciently can we find
the median of those N^2 keys ?
effeciently can we find
the median of those N^2 keys ?
k*r
2 楼
rt
a*m
3 楼
lol. 上周俺正想这个题目呢。 co-等高手解答。
r*e
4 楼
很熟练啊!!
【在 k***r 的大作中提到】
: rt
【在 k***r 的大作中提到】
: rt
f*e
5 楼
我有一个超级傻逼的idea：
把矩形分成两个三角形，左上和右下
左上本来的数据是个minHeap
右下本来的数据是个maxHeap，
把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,
两个heap size一样就能找到median
时间复杂度 O(log(N^2))
把矩形分成两个三角形，左上和右下
左上本来的数据是个minHeap
右下本来的数据是个maxHeap，
把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,
两个heap size一样就能找到median
时间复杂度 O(log(N^2))
a*m
6 楼
lg（n^2）? 那不就是 lg(n)? 不太可能这么快吧。虽然你这个题目有点小小的不一样
，但是还是感觉有问题。
，但是还是感觉有问题。
l*1
7 楼
从左上角的第一个element 开始，count until you have passed N^2/2 elements.
f*e
8 楼
o(n^2)阿
y*g
9 楼
看不懂，，不过log(n^2)就是log(n)
【在 f********e 的大作中提到】
: 我有一个超级傻逼的idea：
: 把矩形分成两个三角形，左上和右下
: 左上本来的数据是个minHeap
: 右下本来的数据是个maxHeap，
: 把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,
: 两个heap size一样就能找到median
: 时间复杂度 O(log(N^2))
【在 f********e 的大作中提到】
: 我有一个超级傻逼的idea：
: 把矩形分成两个三角形，左上和右下
: 左上本来的数据是个minHeap
: 右下本来的数据是个maxHeap，
: 把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,
: 两个heap size一样就能找到median
: 时间复杂度 O(log(N^2))
f*e
10 楼
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 2 3 4
5 6 7
9
左上部分建max heap, 9 is the max
8
10 11 12
13 14 15 16
右下部分建min heap,8 is the min
median = 8/9
但这个方法挺奇怪的
时间复杂度O(logN),heapify
空间复杂度O(N^2)
brute force solution:
time complexity: O(N^2),遍历矩阵
期待大牛给个更好的
5 6 7 8
9 10 11 12
13 14 15 16
1 2 3 4
5 6 7
9
左上部分建max heap, 9 is the max
8
10 11 12
13 14 15 16
右下部分建min heap,8 is the min
median = 8/9
但这个方法挺奇怪的
时间复杂度O(logN),heapify
空间复杂度O(N^2)
brute force solution:
time complexity: O(N^2),遍历矩阵
期待大牛给个更好的
f*4
11 楼
N=5你怎么划分上下？？
用median of medians，N>=5有线性解
http://www.mitbbs.com/article_t0/JobHunting/31971005.html
【在 f********e 的大作中提到】
: 1 2 3 4
: 5 6 7 8
: 9 10 11 12
: 13 14 15 16
: 1 2 3 4
: 5 6 7
: 9
: 左上部分建max heap, 9 is the max
: 8
: 10 11 12
用median of medians，N>=5有线性解
http://www.mitbbs.com/article_t0/JobHunting/31971005.html
【在 f********e 的大作中提到】
: 1 2 3 4
: 5 6 7 8
: 9 10 11 12
: 13 14 15 16
: 1 2 3 4
: 5 6 7
: 9
: 左上部分建max heap, 9 is the max
: 8
: 10 11 12
a*m
12 楼
这样你至少有（n^2）/2个元素要处理，就算每次处理是o(1)也要o(n^2)，你的（lgn）
咋出来的？
【在 f********e 的大作中提到】
: 1 2 3 4
: 5 6 7 8
: 9 10 11 12
: 13 14 15 16
: 1 2 3 4
: 5 6 7
: 9
: 左上部分建max heap, 9 is the max
: 8
: 10 11 12
咋出来的？
【在 f********e 的大作中提到】
: 1 2 3 4
: 5 6 7 8
: 9 10 11 12
: 13 14 15 16
: 1 2 3 4
: 5 6 7
: 9
: 左上部分建max heap, 9 is the max
: 8
: 10 11 12
f*e
13 楼
my bad...谢谢ls指出来
median of medians貌似是个好方法，看看
median of medians貌似是个好方法，看看
g*y
14 楼
这个min-heap, max-heap处理有问题吧，对于一个满足条件的矩阵：
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
你把a11->a14, a21->a23, a31划进左上角，求最大值。
然后右下角，求最小值。
事实上，a14, a41之间，没有确定的大小关系。我不明白这个算法怎么work。
【在 f********e 的大作中提到】
: 1 2 3 4
: 5 6 7 8
: 9 10 11 12
: 13 14 15 16
: 1 2 3 4
: 5 6 7
: 9
: 左上部分建max heap, 9 is the max
: 8
: 10 11 12
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
你把a11->a14, a21->a23, a31划进左上角，求最大值。
然后右下角，求最小值。
事实上，a14, a41之间，没有确定的大小关系。我不明白这个算法怎么work。
【在 f********e 的大作中提到】
: 1 2 3 4
: 5 6 7 8
: 9 10 11 12
: 13 14 15 16
: 1 2 3 4
: 5 6 7
: 9
: 左上部分建max heap, 9 is the max
: 8
: 10 11 12
g*y
15 楼
我不知道median of medians怎么解这道题。
哪怕是这么特殊的矩阵，median of medians不等同于矩阵的median。
【在 f****4 的大作中提到】
: N=5你怎么划分上下？？
: 用median of medians，N>=5有线性解
: http://www.mitbbs.com/article_t0/JobHunting/31971005.html
哪怕是这么特殊的矩阵，median of medians不等同于矩阵的median。
【在 f****4 的大作中提到】
: N=5你怎么划分上下？？
: 用median of medians，N>=5有线性解
: http://www.mitbbs.com/article_t0/JobHunting/31971005.html
B*1
16 楼
大牛，你怎么解这题得啊？
【在 g**********y 的大作中提到】
: 我不知道median of medians怎么解这道题。
: 哪怕是这么特殊的矩阵，median of medians不等同于矩阵的median。
【在 g**********y 的大作中提到】
: 我不知道median of medians怎么解这道题。
: 哪怕是这么特殊的矩阵，median of medians不等同于矩阵的median。
g*y
17 楼
别叫大牛，我不知道有效的办法。我看到的网上的解，好象都有点问题。我也在等牛人
出来给个简单明白的解，或者证明没有太有效的解。
我直觉是对满足条件NxN的矩阵，应该可以在O(N^2)找到median。能在O(N)找到的话，
就是很好的解了。O(logN)，我觉得不太可能。
【在 B*******1 的大作中提到】
: 大牛，你怎么解这题得啊？
出来给个简单明白的解，或者证明没有太有效的解。
我直觉是对满足条件NxN的矩阵，应该可以在O(N^2)找到median。能在O(N)找到的话，
就是很好的解了。O(logN)，我觉得不太可能。
【在 B*******1 的大作中提到】
: 大牛，你怎么解这题得啊？
s*n
18 楼
我能想到的就是A* 类似算法，维护一个heap，没visit一个，要增加两个临近节点，其
实就是在matrix上走，然后着当前最小，不过真是worst case n方，n方 了
【在 g**********y 的大作中提到】
: 别叫大牛，我不知道有效的办法。我看到的网上的解，好象都有点问题。我也在等牛人
: 出来给个简单明白的解，或者证明没有太有效的解。
: 我直觉是对满足条件NxN的矩阵，应该可以在O(N^2)找到median。能在O(N)找到的话，
: 就是很好的解了。O(logN)，我觉得不太可能。
实就是在matrix上走，然后着当前最小，不过真是worst case n方，n方 了
【在 g**********y 的大作中提到】
: 别叫大牛，我不知道有效的办法。我看到的网上的解，好象都有点问题。我也在等牛人
: 出来给个简单明白的解，或者证明没有太有效的解。
: 我直觉是对满足条件NxN的矩阵，应该可以在O(N^2)找到median。能在O(N)找到的话，
: 就是很好的解了。O(logN)，我觉得不太可能。
g*s
19 楼
a NlogN algo was given in:
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
the idea is using weighted median of medians to do partition/filter.
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
the idea is using weighted median of medians to do partition/filter.
B*1
20 楼
这方法面试时候可以code出来吗？
【在 g***s 的大作中提到】
: a NlogN algo was given in:
: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
: the idea is using weighted median of medians to do partition/filter.
【在 g***s 的大作中提到】
: a NlogN algo was given in:
: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
: the idea is using weighted median of medians to do partition/filter.
g*s
21 楼
The codes seem hard but idea is simple. I think once you give the idea, you
got passed.
【在 B*******1 的大作中提到】
: 这方法面试时候可以code出来吗？
got passed.
【在 B*******1 的大作中提到】
: 这方法面试时候可以code出来吗？
f*e
22 楼
you are right！
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pd
【在 g***s 的大作中提到】
: a NlogN algo was given in:
: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
: the idea is using weighted median of medians to do partition/filter.
http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pd
【在 g***s 的大作中提到】
: a NlogN algo was given in:
: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
: the idea is using weighted median of medians to do partition/filter.
f*e
23 楼
牛人能解释一下么？我没看懂，那堆啊a3也提了这样的方法，但我不明白啊。。
【在 f********e 的大作中提到】
: you are right！
: http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pd
【在 f********e 的大作中提到】
: you are right！
: http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pd
l*c
24 楼
career cup 150 has the answer
【在 f********e 的大作中提到】
: We have a N X N matrix whose rows and columns are in sorted order. How
: effeciently can we find
: the median of those N^2 keys ?
【在 f********e 的大作中提到】
: We have a N X N matrix whose rows and columns are in sorted order. How
: effeciently can we find
: the median of those N^2 keys ?
s*7
25 楼
bless.
相关阅读
钻风太desperate了奥巴马吃冰激凌3000日本警察护驾(图)GYM歪想 (转载)Re: 妹妹深夜打电话来说妈妈被送进医院了，可能遭暴力拆迁导致新京报：湖南郴州已拘捕13名"散步"嫌犯zz包公是非洲人？中国特色20个脑筋急转弯童鞋们考试时间到了，请停笔交卷~（转）阿甘见毛泽东原文Hetzer是基佬，长相靓,屁眼松 (转载)回国买房记疑似自杀Re: 答疑：关于在北京招20个quants (转载)Re: 刚看完skyline 很震撼 (转载)我阜宁警方成功赋予“喝茶”新含义zz狄仁杰4看的我真是一口水喷在键盘上├ Re: 强制注销户口Quantitative Easing Explained 笑死 (转载)CS打多了，习惯了进屋前扔个手雷 (转载)丈夫因老婆网名“寂寞少妇”盛怒之下与其扭打