K-Rang-Element unter 2 unsortierten Arrays

Question

Nehmen wir an, wir haben zwei Arrays A [] und B []. Jedes Array enthält n verschiedene ganze Zahlen, die nicht sortiert sind. Wir müssen das k-te Element in der Vereinigung der zwei Arrays auf die effizienteste Weise finden, die möglich ist. (Bitte nicht Beitrag Antworten über die Arrays verschmelzenden ordnen und sortiert dann KTH-Index in der fusionierten Array zurück)

Answer 1

Sie die selection algorithm verwenden können das K-te Element zu finden, in O (N) Zeit, wobei N die Summe der Größen der Arrays. Offensichtlich behandeln Sie die beiden Arrays als ein einzelnes großes Array.

Answer 2

Vereinigung von Arrays kann in linearer Zeit erfolgen. Ich überspringe diesen Teil.

Sie können den partition() Algorithmus verwenden, der in quick sort verwendet wird. Bei der schnellen Sortierung muss die Funktion zwei Zweige rekursiv anzeigen. Hier rufen wir jedoch nur den rekursiven Aufruf und damit nur die 1-verzweigte Rekursion bedingt auf.

Hauptkonzept: partition() den gewählten PIVOT Element an seinem entsprechenden sortiert Position. Daher können wir diese Eigenschaft verwenden, um die Hälfte des Arrays auszuwählen, an der wir interessiert sind, und nur auf diese Hälfte zurückgreifen. Dies verhindert, dass wir das gesamte Array sortieren können.

Ich habe den folgenden Code basierend auf dem oben genannten Konzept geschrieben. Annahme-Rang = 0 impliziert das kleinste Element in dem Array.

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)); 
}