g*********s
发帖数: 1782 | 1 let's assume they all have n elements.
for k = 2, it's classical. but how about the general "k"? |
l*****a
发帖数: 14598 | 2 I can only handle it with
n*K/2*lgk
【在 g*********s 的大作中提到】
: let's assume they all have n elements.
: for k = 2, it's classical. but how about the general "k"?
|
g***s
发帖数: 3811 | 3 Even if it is not sorted, the finding median of all (k*n) item only needs
O(k*n)
【在 l*****a 的大作中提到】
: I can only handle it with
: n*K/2*lgk
|
c**********6
发帖数: 105 | 4 agree
把k个array当作一个用partition algorithm
cheers！！
【在 g***s 的大作中提到】
: Even if it is not sorted, the finding median of all (k*n) item only needs
: O(k*n)
|
f*****w
发帖数: 2602 | |
h**********d
发帖数: 4313 | 6 什么意思，再讲下？
【在 c**********6 的大作中提到】
: agree
: 把k个array当作一个用partition algorithm
: cheers！！
|
l*****a
发帖数: 14598 | 7 could u share your code
thanks
【在 g***s 的大作中提到】
: Even if it is not sorted, the finding median of all (k*n) item only needs
: O(k*n)
|
g***s
发帖数: 3811 | 8 1. put all number into one array, size = k*n O(k*n)
2. find the median of the array O(k*n)
I think LZ is asking for a better solution since the above method doesn't
care if it is sorted or not in the k arrays.
【 在 lolhaha (haha) 的大作中提到: 】 |
g*********s
发帖数: 1782 | 9 yes, for k=2, O(lgN) is surely much better.
doesn't
【在 g***s 的大作中提到】
: 1. put all number into one array, size = k*n O(k*n)
: 2. find the median of the array O(k*n)
: I think LZ is asking for a better solution since the above method doesn't
: care if it is sorted or not in the k arrays.
: 【 在 lolhaha (haha) 的大作中提到: 】
|
n*******p
发帖数: 72 | 10 what if the memory can only hold two arrays rather than all the arrays.
【在 g***s 的大作中提到】
: 1. put all number into one array, size = k*n O(k*n)
: 2. find the median of the array O(k*n)
: I think LZ is asking for a better solution since the above method doesn't
: care if it is sorted or not in the k arrays.
: 【 在 lolhaha (haha) 的大作中提到: 】
|
|
|
j********x
发帖数: 2330 | 11 对每个数组，二分其元素，然后在其他数组中二分查找其左侧（小于）和右侧（大于）
的元素个数
k*O(log^2n)
如果不能同时放入内存，重复上面的过程，每次从载入一个数组即可 |
g***s
发帖数: 3811 | 12 Could not understand:
"然后在其他数组中二分查找其左侧（小于）和右侧（大于）"
what's the '其'?
【在 j********x 的大作中提到】
: 对每个数组，二分其元素，然后在其他数组中二分查找其左侧（小于）和右侧（大于）
: 的元素个数
: k*O(log^2n)
: 如果不能同时放入内存，重复上面的过程，每次从载入一个数组即可
|
a******7
发帖数: 106 | 13 CLRS -> Chapter 9: Medians and Order Statistics -> Selection in worst-case
linear time |
g***s
发帖数: 3811 | 14 here we are discussing a solution better than O(kn) 【 在 anson627 (anson)
的大作中提到: 】
case |
a******7
发帖数: 106 | 15 the book already assumed each sorting in O(1) time, when the sub-array is
small enough. I don't think we can do better in worst case. On average case,
maybe. |
