Trovare un numero maggiore di x in un intervallo

Question

ho un problema che, dopo alcune modifiche riduce a "Trovare il minimo indice del numero maggiore di x in un intervallo [l, r]"

Ad esempio: Supponiamo che un matrice A = {1, 2, 3, 6, 9, 8, 4, 3, 7, 6, 2}

e la query è "trovano almeno indice elemento dell'array a nell'intervallo [2, 6] che è maggiore o uguale a 5"

risposta per la query sopra è 4 (rapporto questo indice è 6) (Gli indici sono basati su 1)

Esistono più query, l'array non è ordinato (si consideri che l'input è già in memoria)

Esiste un algoritmo in cui è possibile eseguire query in O (logN) dove N è no. di elementi nell'array A.

Answer 1

Ci sono in realtà un sacco di modi per supportare le query in tempo O (log N) dopo aver costruito una struttura dati che occupa spazio O (N).

Facile da capire risposta

• Fare un albero binario con gli elementi di A come le foglie, ordinate in base all'indice.
• In ciascun nodo interno, registrare il valore massimo delle foglie nella sottostruttura
• È necessario essere in grado di trovare il percorso di un nodo in base al relativo indice. Se necessario, registrare l'indice della prima foglia in ciascun nodo interno. Puoi andartene senza questo costruendo il tuo albero con una forma conveniente.
• Ora, per trovare il minimo index> = L con un valore> = X:
  • trovare il percorso nella struttura ad A [L]
  • Se A [L] < X, poi salite l'albero finché non trovi uno zio destro che contiene un valore> = X
  • Scendi dall'albero dello zio per trovare la prima foglia con valore> = X. Durante la discesa, se il bambino sinistro ha una foglia> = X (controlla il valore massimo memorizzato), quindi vai a sinistra. Altrimenti vai a destra.

risposta super-efficiente

per rendere l'algoritmo di cui sopra realmente efficace, è possibile codificare l'albero in un array, come facciamo noi per mucchi. In questa rappresentazione (usando indici a 1), si ha una matrice contenente i valori massimi per i nodi interni N-1, seguiti dalle foglie N in ordine. Chiama quell'array H. Quindi i figli di H[i] sono a H[i*2] e H[i*2+1]. Il genitore di H[i] è a H[i>>1]

In pseudocodice, utilizzando 1-base di indici, ci viene dato:

A[] = input array, N = input array size 

Costruiamo H come questo:

H = new array with size N*2-1, indexed from 1 to N*2-1 
for (int i=1; i<=N; ++i) 
    H[i+N-1]=A[i]; 
for (int i=N-1; i>0; --i) 
    H[i] = max(H[2*i],H[2*i+1]); 

Nota che creiamo i bambini davanti ai genitori in modo che i bambini siano lì quando abbiamo bisogno di ottenere il massimo dei loro valori.

Ora, la funzione di query:

//get the index of the first element with val >= minval, index >= minindex, and index <= maxindex 
//returns -1 if there is no such element 

firstAtLeast(minval, minindex, maxindex) 

    if (maxindex < minindex) 
     return -1; 

    node = minindex+N-1; //find minindex in the tree 

    //go up and right until we find a subtree that has a value >= minval 

    while(H[node] < minval) 

     //if we are a right child of our parent, go up until 
     //we have a right sibling 
     while((node&1) == 1) //node is odd 
      node = node>>1; //same as floor(node/2); 
      if (node <= 1) 
       //we went up to the root 
       //there is no such element 
       return -1; 

     //now node is a left child. try its right sibling   
     ++node; 

    //We found a subtree. get the first valid leaf 

    while(node < N) //while it's an internal node 
     node = 2*N; //left child 
     if (H[node] < minval) 
      ++node; //left child not valid - move to right child 

    //Found leaf. get index in A[i] and check against maxindex 

    index = node-(N-1); 
    return (index <= maxindex ? index : -1); 

Questo soddisfa il requisito per le query in O (log N) tempo. Sarebbe bello (e non troppo difficile) uscire presto quando sapete che non ci sarà una risposta inferiore a maxindex, ma ciò renderebbe lo pseudocodice un po 'meno chiaro, quindi lo lascerò come un esercizio

Answer 2

O (logN) cuciture impossibili. È necessario almeno leggere l'input fino al primo elemento che è maggiore (questo potrebbe essere l'ultimo o nessuno). Quindi nel caso peggiore è necessario leggere l'intero input che significa O (N).

I miglioramenti sono possibili solo se c'è qualche struttura in più del vostro ingresso come ordinati di quanto si possa migliorare l'algoritmo di O (log N).

Se ci sono domande multiple, è comunque necessario O (logN). È possibile verificare la presenza di interrogazioni multiple contemporaneamente e anche memorizzare nella cache i risultati per il caso in cui vengono restituite le stesse query.

Answer 3

Se il numero di elementi possibili è piccolo (ad esempio K) e può essere facilmente enumerato, per un array di N elementi, è possibile ordinarli in ordine N + K utilizzando un counting sort. È quindi possibile utilizzare una ricerca binaria per la query, che sarà il registro degli ordini N. Nota l'ordinamento del conteggio richiederà anche la memoria dell'ordine K, e quindi è utile solo quando è in gioco un numero relativamente piccolo di chiavi discrete. Se hai queries Q, la complessità è O ((N + K) + Q (log (N))

Answer 4

Se hai molte domande, con una quantità moderata di dati, potresti essere in grado di ottenere un numero decente speed-up sui vostri dubbi da O (N) l'extra storage.

Creare un aray di tuple (a[i], i) (vale a dire, il valore nella matrice, indice di tale valore), scelte per la prima (e in caso di conflitto, il secondo) in ordine crescente, quindi utilizza la ricerca binaria per trovare il punto di partenza.Se l'indice non rientra nell'intervallo, continua a percorrere l'elenco ordinato finché non trovi un indice che rientra nell'intervallo di tuo interesse

Sospetto che questo algoritmo sia O (N), nel peggiore dei casi, quindi immagino che sia io s possibile fare di meglio.