问大家一个问题, find the kth number in two sorted array

find the kth number in two sorted array

log(n)的解法有木有, 真不知道啊

lg(n)*lg(n)的行不行？

确切说是log(k)*log(k)的....

确切说是log(k)*log(k)的....
tzunami 发表于 2011-11-9 15:28

    log(k)*log(k)怎么做??

等下，有点不严密，我再想想 ...

哦，就是这样，先在第一个数组中用选定一个元素，要下标小于K，然后用二分法在第二个数组中选一个刚好比这个元素小的（还得再选一次大的，常熟加1），在看第一个数组中选定元素之前的元素个数加上第二个数组中搜出的元素之前的个数之和是比K大还是小，要是一样就OK了，要是大，就用二分法在第一个数组中用二分法选择比第一次选择还小的，依次类推，这样就是lgk*lgk了

哦，就是这样，先在第一个数组中用选定一个元素，要下标小于K，然后用二分法在第二个数组中选一个刚好比这个元素小的（还得再选一次大的，常熟加1），在看第一个数组中选定元素之前的元素个数加上第二个数组中搜出的元素之前的个数之和是比K大还是小，要是一样就OK了，要是大，就用二分法在第一个数组中用二分法选择比第一次选择还小的，依次类推，这样就是lgk*lgk了
tzunami 发表于 2011-11-9 16:38

很好, 谢谢
具体逻辑上如果第k个在第二个数组上怎么处理?　做两遍吗？？

做2遍，所以说常数要加1

找中位数的我在网上见过O(logn)的做法

两个数列a,b各自取前k个数 就是a[k],b[k]
比较a[k/2]和b[k/2]
如果前者大，kth数不可能在a[k/2]...a[k]之间，也不可能在b[0]...b[k/2]之间
排除掉这两个子列之后问题归结为在a[0]..a[k/2]和b[k/2]..b[k]之间寻找第k/2个数
所以是个递归算法
rate在log(k)