K排列在2个未分类阵列中的元素

Question

假设我们有两个数组A []和B []。每个数组包含n个不分类的不同整数。我们需要以最有效的方式在2个数组的联合中找到第k个排名元素。 （请不要有关合并的阵列，然后对它们进行排序，以合并后的数组中返回第k个指标后回答）

Answer 1

可以使用selection algorithm找到第K项，在O（n）的时间，其中N是总和的阵列大小。显然，你将这两个数组视为一个大数组。

Answer 2

数组的联合可以在线性时间内完成。我正在跳过这部分。

您可以使用quick sort中使用的partition（）算法。在快速排序中，该功能将不得不递归两个分支。然而，在这里，我们将有条件地调用递归调用，因此只有1分支递归。

主要概念：partition（）将选定的PIVOT元素放置在其适当的排序位置。因此，我们可以使用这个属性来选择我们感兴趣的那个数组的一半，然后在那一半上进行递归。这会阻止我们排序整个数组。

我已经根据上述概念编写了下面的代码。假设秩= 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)); 
}