※ 引述《sincos.bbs@cszone.cc.ntu.edu.tw (簡單生活)》之銘言：
: 有2個integer arrays，Ｘ[1...n] and Ｙ[1...n]，
: each sorted in nondecreasing order。
: 有什麼演算法可以找到 the kth smallest of the 2n combined elements
: 在 Ｏ(logn)之內，where 1≦ k ≦ n ？
: 快想破頭了....！
嘿，這裡有個方法，
事實上，對於任何兩個不同長度的array也適用……
O(log(n1)+log(n2))，n1,n2為兩array的大小
理由跑跑程式看看就知道了
#include <stdio.h>
#define DEBUG 1
//return N({a| a belong to array, a<=x})
int find_place(int x,int * array,int n){
if(n==0) return 0;
if(x>=array[n/2]) return n/2+1+find_place(x,array+n/2+1,(n-1)/2);
else return find_place(x,array,n/2);
}
//if array=combine(array1,array2) return array[k]
int find_k(int k,int * array1,int * array2,int n1,int n2){
if(DEBUG)printf("\n*********************");
if(DEBUG)printf("\narray1=");
if(DEBUG)for(int i=0;i<n1;i++) printf("%d ",array1[i]);
if(DEBUG)printf("\narray2=");
if(DEBUG)for(int i=0;i<n2;i++) printf("%d ",array2[i]);
if(DEBUG)printf("\nWant to find element[%d]!",k);
if(n1==0){
if(DEBUG)printf("\nBecause n1==0 return array2[%d]=%d",k,array2[k]);
return array2[k];
}
int pos=find_place(array1[n1/2],array2,n2);
if(DEBUG)printf("\narray1[%d] is at pos:%d of array2",n1/2,pos);
if(DEBUG)printf("\nSo array1[%d]=%d is element[%d]",n1/2,array1[n1/2],pos+n1/2);
if((pos+n1/2)==k) return array1[n1/2];
else if((pos+n1/2)>k) return find_k(k,array2,array1,pos,n1/2);
else return find_k(k-(pos+n1/2+1),array2+pos,array1+n1/2+1,n2-pos,(n1-1)/2);
}
void main(){
int array1[]={1,5,11,17,21},
array2[]={0,2,4,8,11,19};
int test=find_k(4,array1,array2,5,6);
/* for(int i=0;i<11;i++)
printf("\nfind %d :%d",i,find_k(i,array1,array2,5,6));*/
}
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: h127.s13.ts31.h