---

---

※ 引述《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

--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:44:46