在两个排好序的数组找出第k小的

假设a[m], b[n]是两个排好序的数组,并且没有重复元素,要找第k小的元素
除了用归并找到外还有更好的办法吗?

作者: dreamhunter_lan   发布时间: 2011-06-14

也可以不归并,直接利用这两个原有的数组直接比较。具体的做法是:利用一个循环语句,比较a[i]和b[i],对断参数j进行 j+2, 下来对k(k:指k小元素),然后再利用if判断k和j的关系。这样就能得到结果。感觉这样还可以,至于好不好就不好说了。

作者: fengchaokobe   发布时间: 2011-06-14

相关的代码如下:
C/C++ code

int j = 0;//判断参数
    for(i = 0; i < n; i++)
        if(a[i] > b[i])
        {
            min = b[i];
            max = a[i];
        }
        else
        {
            min = a[i];
            max = b[i];
        }
        j = j + 2if(j >= k)//判断第k小元素是否在a[i]或b[i]中
        {
            if(j - k == 0)
                printf:the kth number is: max
            else
                printf:the kth number is: min
        }



请各位指点!

作者: fengchaokobe   发布时间: 2011-06-14

to楼上:
a 1 2 3
b 4 5 6
k = 4

i=0: 4>1 max=4, min=1 j=j+2=2
j<k

i=1: 5>2 max=5, min=2 j=j+2=4
最后返回5了
下面的不说了

作者: dreamhunter_lan   发布时间: 2011-06-14

lz,这次还是二分,你不妨多想想,log(n)的。

引用楼主 dreamhunter_lan 的回复:
假设a[m], b[n]是两个排好序的数组,并且没有重复元素,要找第k小的元素
除了用归并找到外还有更好的办法吗?

作者: litaoye   发布时间: 2011-06-14

int t = 0;
int i , j = 0;
while ( a[i] < b[j]
  i++;
else
  j++
t++;
if (t == k)
  return 

思路就是这样,

作者: bryantism   发布时间: 2011-06-14