Attribuite 2 array ordinati di interi, trovano il maggior numero ennesima in tempo sublineare

Question

Eventuali duplicati:
How to find the kth smallest element in the union of two sorted arrays?

Questa è una domanda uno dei miei amici mi ha detto che è stato chiesto, mentre intervistando, ho pensato a una soluzione.

Il tempo sub-lineare implica logaritmico per me, quindi forse una sorta di metodo divide et impera. Per semplicità, diciamo che entrambi gli array hanno le stesse dimensioni e che tutti gli elementi sono unici

Answer 1

credo che questo sia due ricerche binarie simultanei sui sottoarray A[0..n-1] e B[0..n-1], che è O (log n).

• array ordinati dato, si sa che il ennesima più grande apparirà da qualche parte prima o A[n-1] se è in ordine A, o B[n-1] se è in serie B
• Considerare elemento di indice a in A e articolo all'indice b in B.
• Esegui ricerca binaria come segue (pseudocodice piuttosto grezzi, non prendendo in considerazione 'una tantum' problemi):
  • Se a + b > n, poi ridurre impostare la ricerca
    • se A[a] > B[b] poi b = b/2, altrimenti a = a/2
  • Se a + b < n, quindi aumentare impostare la ricerca
    • se A[a] > B[b] quindi b = 3/2 * b, altrimenti a = 3/2 * a (a metà strada tra a e precedente a)
  • Se a + b = n poi il ennesima più grande è max(A[a], B[b])

Credo caso peggiore O (ln n), ma in ogni caso decisamente sublimatico.

Answer 2

Credo che sia possibile risolvere questo problema utilizzando una variante sulla ricerca binaria. L'intuizione dietro questo algoritmo è la seguente. Lascia che i due array siano A e B e assumiamo per semplicità che hanno le stesse dimensioni (non è necessario, come vedrai). Per ogni array, possiamo costruire array paralleli Ac e Bc in modo tale che per ogni indice i, Ac [i] sia il numero di elementi nei due array che non sono più grandi di A [i] e Bc [i] è il numero di elementi nei due array non più grandi di B [i]. Se potessimo costruire questi array in modo efficiente, potremmo trovare il kth più piccolo elemento in modo efficiente facendo ricerche binarie sia su Ac che su Bc per trovare il valore k. La voce corrispondente di A o B per quella voce è quindi il kesimo elemento più grande. La ricerca binaria è valida perché i due array Ac e Bc sono ordinati, il che credo si possa convincere abbastanza facilmente.

Ovviamente, questa soluzione non funziona in tempo sublinear perché richiede O (n) tempo per costruire gli array Ac e Bc. La domanda allora è - c'è un modo che possiamo implicitamente costruire questi array? Cioè, possiamo determinare i valori in questi array senza necessariamente costruire ciascun elemento? I penso che che la risposta è sì, usando questo algoritmo. Iniziamo cercando l'array A per vedere se ha il kth valore più piccolo. Sappiamo per certo che il k più piccolo valore non può apparire nell'array nell'array A dopo la posizione k (assumendo che tutti gli elementi siano distinti). Quindi concentriamoci solo sui primi k elementi dell'array A. Effettueremo una ricerca binaria su questi valori come segue. Inizia alla posizione k/2; questo è il k/2 ° elemento più piccolo nell'array A. Ora fai una ricerca binaria nell'array B per trovare il valore più grande in B più piccolo di questo valore e osserva la sua posizione nell'array; questo è il numero di elementi in B più piccoli del valore corrente. Se sommiamo la posizione degli elementi in A e B, abbiamo il numero totale di elementi nei due array più piccoli dell'elemento corrente. Se questo è esattamente k, abbiamo finito. Se questo è minore di k, allora ricorsiamo nella metà superiore dei primi k elementi di A, e se questo è maggiore di k ricorsiamo nella metà inferiore dei primi elementi di k, ecc. Alla fine, saremo entrambi trova che il k più grande elemento è nella matrice A, nel qual caso abbiamo finito. Altrimenti, ripetere questo processo sull'array B.

Il runtime per questo algoritmo è il seguente. La ricerca dell'array A esegue una ricerca binaria su k elementi, che prende le iterazioni di O (lg k). Ogni iterazione costa O (lg n), dal momento che dobbiamo eseguire una ricerca binaria in B. Ciò significa che il tempo totale per questa ricerca è O (lg k lg n). Il tempo per farlo nell'array B è lo stesso, quindi il runtime netto per l'algoritmo è O (lg k lg n) = O (lg n) = o (n), che è sublineare.

Answer 3

Sublinear di cosa? Non è possibile avere un algoritmo che non controlli almeno n elementi, anche la verifica di una soluzione richiede il controllo di molti. Ma la dimensione del problema qui dovrebbe sicuramente significare la dimensione degli array, quindi un algoritmo che controlla solo n elementi è sublineare.

Quindi penso che ci sia nessun trucco qui, cominciare con l'elenco con l'elemento di partenza più piccolo e avanzare fino a quando non sia:

1. Raggiungere l'elemento n-esimo, e il gioco è fatto.
2. Trova l'elemento successivo più grande dell'elemento successivo nell'altro elenco, a quel punto si passa all'altro elenco.
3. Esaurito da elementi e interruttore.

Answer 4

int[] a = new int[] { 11, 9, 7, 5, 3 }; 
int[] b = new int[] { 12, 10, 8, 6, 4 }; 
int n = 7; 
int result = 0; 
if (n > (a.Length + b.Length)) 
    throw new Exception("n is greater than a.Length + b.Length"); 
else if (n < (a.Length + b.Length)/2) 
{ 
    int ai = 0; 
    int bi = 0; 
    for (int i = n; i > 0; i--) 
    { 
     // find the highest from a or b 
     if (ai < a.Length) 
     { 
      if (bi < b.Length) 
      { 
       if (a[ai] > b[bi]) 
       { 
        result = a[ai]; 
        ai++; 
       } 
       else 
       { 
        result = b[bi]; 
        bi++; 
       } 
      } 
      else 
      { 
       result = a[ai]; 
       ai++; 
      } 
     } 
     else 
     { 
      if (bi < b.Length) 
      { 
       result = b[bi]; 
       bi++; 
      } 
      else 
      { 
       // error, n is greater than a.Length + b.Length 
      } 
     } 
    } 
} 
else 
{ 
    // go in reverse 
    int ai = a.Length - 1; 
    int bi = b.Length - 1; 
    for (int i = a.Length + b.Length - n; i >= 0; i--) 
    { 
     // find the lowset from a or b 
     if (ai >= 0) 
     { 
      if (bi >= 0) 
      { 
       if (a[ai] < b[bi]) 
       { 
        result = a[ai]; 
        ai--; 
       } 
       else 
       { 
        result = b[bi]; 
        bi--; 
       } 
      } 
      else 
      { 
       result = a[ai]; 
       ai--; 
      } 
     } 
     else 
     { 
      if (bi >= 0) 
      { 
       result = b[bi]; 
       bi--; 
      } 
      else 
      { 
       // error, n is greater than a.Length + b.Length 
      } 
     } 
    } 
} 
Console.WriteLine("{0} th highest = {1}", n, result); 

Answer 5

Questa è una risposta abbastanza simile a quella di Kirk.

Lasciate Find(nth, A, B) essere la funzione che restituisce l'ennesimo numero e | A | + | B | > = n. Questo è un semplice pseudo codice senza verificare se uno degli array è piccolo, meno di 3 elementi. In caso di array di piccole dimensioni, una o due ricerche binarie in array più grandi sono sufficienti per trovare l'elemento necessario.

Find(nth, A, B) 
    If A.last() <= B.first(): 
    return B[nth - A.size()] 
    If B.last() <= A.first(): 
    return A[nth - B.size()] 
    Let a and b indexes of middle elements of A and B 
    Assume that A[a] <= B[b] (if not swap arrays) 
    if nth <= a + b: 
    return Find(nth, A, B.first_half(b)) 
    return Find(nth - a, A.second_half(a), B) 

È log(|A|) + log(|B|), e perché gli array di input possono essere fatte per avere n elementi ciascuno è log(n) complessità.