w**********8
发帖数: 121 | 1 Given three sorted arrays, A, B, C, each of length n (assume odd), with all
3n elements distinct, find the median of the 3n elements.
O(n) time is easy to do. Is there an O(logn) time algorithm? | r****c
发帖数: 2585 | 2 basic idea, for three sorted arrays of A_1, A_2, A_3 (arbitratry length), (
assume you already know the smallest n_1 numbers and largest n_2 number),
find the longest one and choose the medium, say K in A_1, then find K's
position in all other two. Now you know K's position in all 3n, if it is <
3n/2 then the mediam then update to exclude all numbers smaller than K in
three arrays, and update n_1 = n_1 + all numbers smaller than K. recursion
then
so every time, you reduce the size at least by 5/
【在 w**********8 的大作中提到】
: Given three sorted arrays, A, B, C, each of length n (assume odd), with all
: 3n elements distinct, find the median of the 3n elements.
: O(n) time is easy to do. Is there an O(logn) time algorithm?
| c*******d
发帖数: 255 | 3 T(n) = T(5/6 n) + 2 log(n)
根据Master method, T(n) = [log(n)]^2
不知我的理解对不对？
【在 r****c 的大作中提到】
: basic idea, for three sorted arrays of A_1, A_2, A_3 (arbitratry length), (
: assume you already know the smallest n_1 numbers and largest n_2 number),
: find the longest one and choose the medium, say K in A_1, then find K's
: position in all other two. Now you know K's position in all 3n, if it is <
: 3n/2 then the mediam then update to exclude all numbers smaller than K in
: three arrays, and update n_1 = n_1 + all numbers smaller than K. recursion
: then
: so every time, you reduce the size at least by 5/
| x***y
发帖数: 633 | 4 we can reduce it to 2 arrays problem...First compare the median of 3 arrays, if A[n/2]
C[0:n/2-1] together, we can find the median of these two in logn, compare
it witht the median of B, eliminate corresponding part of B and A, C
combination. To do it in A, C combination, we have to find the position of
median in both A and C, O(logn) time. This B and A,C combination is just a 2
array problem except to find median and do e
【在 w**********8 的大作中提到】
: Given three sorted arrays, A, B, C, each of length n (assume odd), with all
: 3n elements distinct, find the median of the 3n elements.
: O(n) time is easy to do. Is there an O(logn) time algorithm?
| x***y
发帖数: 633 | 5 Actually, we can do some extension. For m arrays, we can convert to m-1
arrays problem with the time complexity being timed O(logn). Then, convert
into m-2 arrays, m-3 arrays, and in the end 2 arrays, which is O(logn), 1 array
which is O(1), we can conclude that the time efficiency is O((logn)^(m-1)) for m arrays with same length m.
Also, this can be extended into arrays with different lengths as two arrays with different lengths..... | w**********8
发帖数: 121 | 6 so every time, you reduce the size at least by 5/6, log n will do that.
****************
this is not log(n) because log(n) has 2 as the base which means each time
you get rid of half of the rest.
【在 r****c 的大作中提到】
: basic idea, for three sorted arrays of A_1, A_2, A_3 (arbitratry length), (
: assume you already know the smallest n_1 numbers and largest n_2 number),
: find the longest one and choose the medium, say K in A_1, then find K's
: position in all other two. Now you know K's position in all 3n, if it is <
: 3n/2 then the mediam then update to exclude all numbers smaller than K in
: three arrays, and update n_1 = n_1 + all numbers smaller than K. recursion
: then
: so every time, you reduce the size at least by 5/
| w**********8
发帖数: 121 | 7 I was trying to reduce the problem to 2 arrays but I did not succeed. In
your solution, even if you find median of A and C. How do you compare it
with B to find the median of A, B,C.
A:1 4 6 10 18
B:22 28 33 45 58
C:7 9 100 180 200
you find the median of A and C is 9 or 10. Tell me how do you use them to
find the median of 3 arrays.
arrays, if A[n/2]
A[n/2:n-1] and
2
【在 x***y 的大作中提到】
: we can reduce it to 2 arrays problem...First compare the median of 3 arrays, if A[n/2]: C[0:n/2-1] together, we can find the median of these two in logn, compare
: it witht the median of B, eliminate corresponding part of B and A, C
: combination. To do it in A, C combination, we have to find the position of
: median in both A and C, O(logn) time. This B and A,C combination is just a 2
: array problem except to find median and do e
| w**********8
发帖数: 121 | 8 I am thinking this way.
let n = 2m +1;
* Let three median are Am, Bm, Cm
* compare them, let Am < Bm < Cm
* get rid of 0 ... m in A, and m ... n-1 in C
* for the rest of arrays, repeat the 3 steps above.
each time, we get rid of 2/6 of the rest numbers, i.e. T(n) = C+T(2n/3). This
is not O(log(n)) as well.
That's the best I can gave. Any other ideas?
【在 r****c 的大作中提到】
: basic idea, for three sorted arrays of A_1, A_2, A_3 (arbitratry length), (
: assume you already know the smallest n_1 numbers and largest n_2 number),
: find the longest one and choose the medium, say K in A_1, then find K's
: position in all other two. Now you know K's position in all 3n, if it is <
: 3n/2 then the mediam then update to exclude all numbers smaller than K in
: three arrays, and update n_1 = n_1 + all numbers smaller than K. recursion
: then
: so every time, you reduce the size at least by 5/
| c*******d
发帖数: 255 | 9 base 2 or base e doesn't matter
just a difference in the constant coefficient
【在 w**********8 的大作中提到】
: so every time, you reduce the size at least by 5/6, log n will do that.
: ****************
: this is not log(n) because log(n) has 2 as the base which means each time
: you get rid of half of the rest.
| c*******d
发帖数: 255 | 10
下一步A, B, C的size分别是m, 2m, m（不同长度），和初始的情况不一样了
This
如果这个recursion是对的，当然是log(n)
google "Master method recursion"
【在 w**********8 的大作中提到】
: I am thinking this way.
: let n = 2m +1;
: * Let three median are Am, Bm, Cm
: * compare them, let Am < Bm < Cm
: * get rid of 0 ... m in A, and m ... n-1 in C
: * for the rest of arrays, repeat the 3 steps above.
: each time, we get rid of 2/6 of the rest numbers, i.e. T(n) = C+T(2n/3). This
: is not O(log(n)) as well.
: That's the best I can gave. Any other ideas?
| r****c
发帖数: 2585 | 11 it is not absolute right,
since the number of elements are not same for three arrays, your method does
not work well in degraded case
This
【在 w**********8 的大作中提到】
: I am thinking this way.
: let n = 2m +1;
: * Let three median are Am, Bm, Cm
: * compare them, let Am < Bm < Cm
: * get rid of 0 ... m in A, and m ... n-1 in C
: * for the rest of arrays, repeat the 3 steps above.
: each time, we get rid of 2/6 of the rest numbers, i.e. T(n) = C+T(2n/3). This
: is not O(log(n)) as well.
: That's the best I can gave. Any other ideas?
| w**********8
发帖数: 121 | 12 Thanks. You are right. "下一步A, B, C的size分别是m, 2m, m（不同长度），和初
始的情况不一样了"
But master theorem shows T(n/b) is not log(n) if b != 2.
http://en.wikipedia.org/wiki/Master_theorem
【在 c*******d 的大作中提到】
:
: 下一步A, B, C的size分别是m, 2m, m（不同长度），和初始的情况不一样了
: This
: 如果这个recursion是对的，当然是log(n)
: google "Master method recursion"
| w**********8
发帖数: 121 | 13 what is degrade case? could you give one example?
does
【在 r****c 的大作中提到】
: it is not absolute right,
: since the number of elements are not same for three arrays, your method does
: not work well in degraded case
:
: This
| x***y
发帖数: 633 | 14 A[n/2]=6, B[n/2]=33, C[n/2]=100, So A':6 10 18 C': 7 9
To find the median M' of A' C', O(log(max(|A'|, |C'|)))=O(logn).
if M' < B[n/2], B is left with B[22 28 33], and find data in A'less than M'
, find data in C' less than M', O(logn), and eleminate them.....
All problems of this kind is essentially 2 array problem, and the time
efficiency is O(logn) * time for finding the median and delete operation in each array. For sorted array, 2nd term is O(1), but for an partially sorted array A'+C',th
【在 w**********8 的大作中提到】
: I was trying to reduce the problem to 2 arrays but I did not succeed. In
: your solution, even if you find median of A and C. How do you compare it
: with B to find the median of A, B,C.
: A:1 4 6 10 18
: B:22 28 33 45 58
: C:7 9 100 180 200
: you find the median of A and C is 9 or 10. Tell me how do you use them to
: find the median of 3 arrays.
:
: arrays, if A[n/2]
|
|
