在两个排好序的数组找出第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
请各位指点!
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 + 2; if(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了
下面的不说了
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小的元素
除了用归并找到外还有更好的办法吗?
假设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
思路就是这样,
int i , j = 0;
while ( a[i] < b[j]
i++;
else
j++
t++;
if (t == k)
return
思路就是这样,
作者: bryantism 发布时间: 2011-06-14