哥独自悲伤去了# Joke - 肚皮舞运动f*e2011-07-28 07:071 楼We have a N X N matrix whose rows and columns are in sorted order. Howeffeciently can we findthe median of those N^2 keys ?
f*e2011-07-28 07:075 楼我有一个超级傻逼的idea:把矩形分成两个三角形,左上和右下左上本来的数据是个minHeap右下本来的数据是个maxHeap,把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,两个heap size一样就能找到median时间复杂度 O(log(N^2))
y*g2011-07-28 07:079 楼看不懂,,不过log(n^2)就是log(n)【在 f********e 的大作中提到】: 我有一个超级傻逼的idea:: 把矩形分成两个三角形,左上和右下: 左上本来的数据是个minHeap: 右下本来的数据是个maxHeap,: 把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,: 两个heap size一样就能找到median: 时间复杂度 O(log(N^2))
f*e2011-07-28 07:0710 楼1 2 3 45 6 7 89 10 11 1213 14 15 161 2 3 45 6 79 左上部分建max heap, 9 is the max810 11 1213 14 15 16右下部分建min heap,8 is the minmedian = 8/9但这个方法挺奇怪的时间复杂度O(logN),heapify空间复杂度O(N^2)brute force solution:time complexity: O(N^2),遍历矩阵期待大牛给个更好的
f*42011-07-28 07:0711 楼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
a*m2011-07-28 07:0712 楼这样你至少有(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
g*y2011-07-28 07:0714 楼这个min-heap, max-heap处理有问题吧,对于一个满足条件的矩阵:a11 a12 a13 a14a21 a22 a23 a24a31 a32 a33 a34a41 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*y2011-07-28 07:0715 楼我不知道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
B*12011-07-28 07:0716 楼大牛,你怎么解这题得啊?【在 g**********y 的大作中提到】: 我不知道median of medians怎么解这道题。: 哪怕是这么特殊的矩阵,median of medians不等同于矩阵的median。
g*y2011-07-28 07:0717 楼别叫大牛,我不知道有效的办法。我看到的网上的解,好象都有点问题。我也在等牛人出来给个简单明白的解,或者证明没有太有效的解。我直觉是对满足条件NxN的矩阵,应该可以在O(N^2)找到median。能在O(N)找到的话,就是很好的解了。O(logN),我觉得不太可能。【在 B*******1 的大作中提到】: 大牛,你怎么解这题得啊?
s*n2011-07-28 07:0718 楼我能想到的就是A* 类似算法,维护一个heap,没visit一个,要增加两个临近节点,其实就是在matrix上走,然后着当前最小,不过真是worst case n方,n方 了【在 g**********y 的大作中提到】: 别叫大牛,我不知道有效的办法。我看到的网上的解,好象都有点问题。我也在等牛人: 出来给个简单明白的解,或者证明没有太有效的解。: 我直觉是对满足条件NxN的矩阵,应该可以在O(N^2)找到median。能在O(N)找到的话,: 就是很好的解了。O(logN),我觉得不太可能。
g*s2011-07-28 07:0719 楼a NlogN algo was given in:http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=rithe idea is using weighted median of medians to do partition/filter.
B*12011-07-28 07:0720 楼这方法面试时候可以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*s2011-07-28 07:0721 楼The codes seem hard but idea is simple. I think once you give the idea, yougot passed.【在 B*******1 的大作中提到】: 这方法面试时候可以code出来吗?
f*e2011-07-28 07:0722 楼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.
f*e2011-07-28 07:0723 楼牛人能解释一下么?我没看懂,那堆啊a3也提了这样的方法,但我不明白啊。。【在 f********e 的大作中提到】: you are right!: http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pd
l*c2011-07-28 07:0724 楼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 ?