r****o
发帖数: 1950 | 1 感觉应该有类似binary search的方法, 复杂度O(lgn)，
但具体细节还是不清楚。
有谁知道怎么作吗？ |
m******9
发帖数: 968 | 2 这个可以log2k找到
你从array 1中取前k个数, 从array2中也取前k个数. 然后对取出来的这2个子数组, 找
median, 就是整个array1和array2的kth min了 |
r****o
发帖数: 1950 | 3 多谢。如果某个array长度不到k怎么办呢?
【在 m******9 的大作中提到】
: 这个可以log2k找到
: 你从array 1中取前k个数, 从array2中也取前k个数. 然后对取出来的这2个子数组, 找
: median, 就是整个array1和array2的kth min了
|
g********n
发帖数: 127 | 4 Then go to the second array to find k+r elements (in which r = k - length_
1st_array).
【在 r****o 的大作中提到】
: 多谢。如果某个array长度不到k怎么办呢?
|
r****o
发帖数: 1950 | 5 没看明白，能解释一下吗?
【在 g********n 的大作中提到】
: Then go to the second array to find k+r elements (in which r = k - length_
: 1st_array).
|
y**i
发帖数: 1112 | 6 不能merge同时计数么，到第k个的时候停止，就是要找的数了
【在 m******9 的大作中提到】
: 这个可以log2k找到
: 你从array 1中取前k个数, 从array2中也取前k个数. 然后对取出来的这2个子数组, 找
: median, 就是整个array1和array2的kth min了
|
r****o
发帖数: 1950 | 7 这个是O(k)啊，应该有O(lgK)的方法。
【在 y**i 的大作中提到】
: 不能merge同时计数么，到第k个的时候停止，就是要找的数了
|
m******9
发帖数: 968 | 8 他说的是对的.
用log(m+n)找median可以看看这个帖子:
http://geeksforgeeks.org/?p=2105
意思就是, 你要取2组sub array, 使得它们的元素总个数是2k, 此时当你找到median时
,自然就是
kth min了. 对2个sorted array找median in log(m+n), 可以参考一下上面那个连接
【在 r****o 的大作中提到】
: 这个是O(k)啊，应该有O(lgK)的方法。
|
r****o
发帖数: 1950 | 9 明白了，多谢。
不过，如果第2个数组不够长(也就是说，第2个数组长度>k，第一个数组长度
两个数组总长度还是<2k）的话，这个方法还是不行把。
【在 m******9 的大作中提到】
: 他说的是对的.
: 用log(m+n)找median可以看看这个帖子:
: http://geeksforgeeks.org/?p=2105
: 意思就是, 你要取2组sub array, 使得它们的元素总个数是2k, 此时当你找到median时
: ,自然就是
: kth min了. 对2个sorted array找median in log(m+n), 可以参考一下上面那个连接
|
h**6
发帖数: 4160 | 10 碰上两个数组总长度不够2k的情况，那么就找第m大的，这时必然有m |
m****n
发帖数: 589 | 11 能再解释一下吗？
我没懂
找第m大，然后呢？
【在 h**6 的大作中提到】
: 碰上两个数组总长度不够2k的情况，那么就找第m大的，这时必然有m
|
r********9
发帖数: 1116 | 12 这个是2klogn+log2k吧?
【在 m******9 的大作中提到】
: 这个可以log2k找到
: 你从array 1中取前k个数, 从array2中也取前k个数. 然后对取出来的这2个子数组, 找
: median, 就是整个array1和array2的kth min了
|
b******n
发帖数: 823 | 13 http://www.mitbbs.com/article/JobHunting/31548441_0.html
每个array取第k/2个元素比较，假设array1较小，那么array1的前k/2个元素必然在2个
array的前k小中，干掉这k/2个元素，找2个array剩下的第k/2小元素，recursion。
log k |
