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

两个数列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)

我不知道问题有没有理解对

两个数列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)

我不知道问题有没有理解对
剑魔独孤求败 发表于 2011-11-10 10:24

大概思路是这样。不过还可以optimize。

思路跟代码在这里。
http://www.leetcode.com/2011/01/ ... nt-in-union-of.html

mitbbs上找到的：

1. 
   
2. int a[maxn],b[maxn];
   
3. 
   
4. int find(int aleft,int aright,int bleft,int bright,int k) {
   
5.     if ((aright-aleft+1)+(bright-bleft+1)<k) {
   
6.         cout<<"error"<<endl;
   
7.         return 0;
   
8.     }
   
9.     if (aleft>aright)
   
10.         return b[bleft+k-1];
    
11.     if (bleft>bright)
    
12.         return a[aleft+k-1];
    
13.     int amid=(aleft+aright)>>1;
    
14.     int bmid=(bleft+bright)>>1;
    
15.     if (a[amid]<=b[bmid])
    
16.         if (k<=(amid-aleft)+(bmid-bleft)+1)
    
17.             return find(aleft,aright,bleft,bmid-1,k);
    
18.         else
    
19.             return find(amid+1,aright,bleft,bright,k-(amid-aleft+1));
    
20.     else
    
21.         if (k<=(amid-aleft)+(bmid-bleft)+1)
    
22.             return find(aleft,amid-1,bleft,bright,k);
    
23.         else
    
24.             return find(aleft,aright,bmid+1,bright,k-(bmid-bleft+1));
    
25. }
    

复制代码