2番目の配列されていない配列の中のK番目の要素

Question

2つの配列A []とB []があるとします。各配列にはソートされていないn個の異なる整数が含まれています。可能な限り最も効率的な方法で、2番目の配列の和集合でk番目にランクされた要素を見つける必要があります。 （配列をマージして、マージされた配列内のk番目のインデックスを返すために、それらを仕分けについてのポストの答えをいけないしてください）

Answer 1

あなたはNの和であるO（N）時間、で、K番目の項目を見つけるためにselection algorithmを使用することができますの配列のサイズの。明らかに、2つの配列を1つの大きな配列として扱います。

Answer 2

アレイの連合は線形時間で行うことができます。私はその部分をスキップしています。

quick sortで使用されているpartition（）アルゴリズムを使用できます。クイックソートでは、関数は2つのブランチを再帰しなければなりません。しかしここでは、条件付きで再帰呼び出しを呼び出すため、1分枝再帰のみが呼び出されます。

メインコンセプト：partition（）は、選択したPIVOT要素を適切なソートされた位置に配置します。したがって、このプロパティを使用して、興味のある配列の半分を選択し、その半分だけを再帰させることができます。これにより、配列全体をソートすることができなくなります。

私は上記の考え方に基づいて以下のコードを書いています。 Assumation rank = 0は配列の最小要素を意味します。

void swap (int *a, int *b) 
{ 
    int tmp = *a; 
    *a = *b; 
    *b = tmp; 
} 

int partition (int a[], int start, int end) 
{ 
    /* choose a fixed pivot for now */ 
    int pivot = a[end]; 
    int i = start, j; 

    for (j = start; j <= end-1; j++) { 
     if (a[j] < pivot) { 
      swap (&a[i], &a[j]); 
      i++; 
     } 
    } 
    /* Now swap the ith element with the pivot */ 
    swap (&a[i], &a[end]); 
    return i; 
} 

int find_k_rank (int a[], int start, int end, int k) 
{ 
    int x = partition (a, start, end); 
    if (x == k) { 
     return a[x]; 
    } else if (k < x) { 
     return find_k_rank (a, start, x-1, k); 
    } else { 
     return find_k_rank (a, x+1, end, k); 
    } 
} 

int main() 
{ 
    int a[] = {10,2,7,4,8,3,1,5,9,6}; 
    int N = 10; 
    int rank = 3; 
    printf ("%d\n", find_k_rank (a, 0, N-1, rank)); 
}