f********e
发帖数: 166 | 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 ? |
a********m
发帖数: 15480 | 2 lol. 上周俺正想这个题目呢。 co-等高手解答。 |
f********e
发帖数: 166 | 3 我有一个超级傻逼的idea：
把矩形分成两个三角形，左上和右下
左上本来的数据是个minHeap
右下本来的数据是个maxHeap，
把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,
两个heap size一样就能找到median
时间复杂度 O(log(N^2)) |
a********m
发帖数: 15480 | 4 lg（n^2）? 那不就是 lg(n)? 不太可能这么快吧。虽然你这个题目有点小小的不一样
，但是还是感觉有问题。 |
l*******1
发帖数: 113 | 5 从左上角的第一个element 开始，count until you have passed N^2/2 elements. |
f********e
发帖数: 166 | |
y*******g
发帖数: 6599 | 7 看不懂，，不过log(n^2)就是log(n)
【在 f********e 的大作中提到】
: 我有一个超级傻逼的idea：
: 把矩形分成两个三角形，左上和右下
: 左上本来的数据是个minHeap
: 右下本来的数据是个maxHeap，
: 把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,
: 两个heap size一样就能找到median
: 时间复杂度 O(log(N^2))
|
f********e
发帖数: 166 | 8 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),遍历矩阵
期待大牛给个更好的 |
f****4
发帖数: 1359 | 9 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********m
发帖数: 15480 | 10 这样你至少有（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
发帖数: 166 | 11 my bad...谢谢ls指出来
median of medians貌似是个好方法，看看 |
g**********y
发帖数: 14569 | 12 这个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
|
g**********y
发帖数: 14569 | 13 我不知道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*******1
发帖数: 2454 | 14 大牛，你怎么解这题得啊？
【在 g**********y 的大作中提到】
: 我不知道median of medians怎么解这道题。
: 哪怕是这么特殊的矩阵，median of medians不等同于矩阵的median。
|
g**********y
发帖数: 14569 | 15 别叫大牛，我不知道有效的办法。我看到的网上的解，好象都有点问题。我也在等牛人
出来给个简单明白的解，或者证明没有太有效的解。
我直觉是对满足条件NxN的矩阵，应该可以在O(N^2)找到median。能在O(N)找到的话，
就是很好的解了。O(logN)，我觉得不太可能。
【在 B*******1 的大作中提到】
: 大牛，你怎么解这题得啊？
|
s******n
发帖数: 226 | 16 我能想到的就是A* 类似算法，维护一个heap，没visit一个，要增加两个临近节点，其
实就是在matrix上走，然后着当前最小，不过真是worst case n方，n方 了
【在 g**********y 的大作中提到】
: 别叫大牛，我不知道有效的办法。我看到的网上的解，好象都有点问题。我也在等牛人
: 出来给个简单明白的解，或者证明没有太有效的解。
: 我直觉是对满足条件NxN的矩阵，应该可以在O(N^2)找到median。能在O(N)找到的话，
: 就是很好的解了。O(logN)，我觉得不太可能。
|
g***s
发帖数: 3811 | 17 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. |
B*******1
发帖数: 2454 | 18 这方法面试时候可以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
发帖数: 3811 | 19 The codes seem hard but idea is simple. I think once you give the idea, you
got passed.
【在 B*******1 的大作中提到】
: 这方法面试时候可以code出来吗？
|
f********e
发帖数: 166 | 20 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********e
发帖数: 166 | 21 牛人能解释一下么？我没看懂，那堆啊a3也提了这样的方法，但我不明白啊。。
【在 f********e 的大作中提到】
: you are right！
: http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pd
|
l******c
发帖数: 2555 | 22 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 ?
|
s********7
发帖数: 4681 | |
