由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 一个算法题:Selecting median of three sorted arrays
相关主题
M大小的数组中选出前N个元素 (如果M和N都很大)MS a0, a1, ..., b0, b1... 问题
median of K sorted array优步面试,哎。。。
找2个sorted array中的第K小的元素,有O(lgn)方法吗?The time complexity on finding the kth largest element in a
Find the Kth smallest element in 2 sorted一个小公司面经
find median for k sorted arrays问一道老题
问一道google的题amazon的一道题
找第K个最小的元素Quick sort为什么需要logN的memory?
刷题刷到没自信了Facebook interview questions
相关话题的讨论汇总
话题: arrays话题: median话题: logn话题: find话题: sorted
进入JobHunting版参与讨论
1 (共1页)
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]
1 (共1页)
进入JobHunting版参与讨论
相关主题
Facebook interview questionsfind median for k sorted arrays
Amazon二面问一道google的题
发facebook两轮面经,求第三轮经验找第K个最小的元素
请教一道题刷题刷到没自信了
M大小的数组中选出前N个元素 (如果M和N都很大)MS a0, a1, ..., b0, b1... 问题
median of K sorted array优步面试,哎。。。
找2个sorted array中的第K小的元素,有O(lgn)方法吗?The time complexity on finding the kth largest element in a
Find the Kth smallest element in 2 sorted一个小公司面经
相关话题的讨论汇总
话题: arrays话题: median话题: logn话题: find话题: sorted