Trova il primo numero maggiore di un dato in una sequenza non ordinata

Question

Data una sequenza di numeri interi positivi e un numero intero M, restituisce il primo numero nella sequenza che è maggiore di M (o -1 se non esiste) .

Esempio: sequenza = [2, 50, 8, 9, 1], M = 3 -> ritorno = 50

O (log n) per ogni query richiesta (dopo preelaborazione).

ho pensato di BST, ma dato una sequenza ascendente che avrei avuto solo un lungo percorso, che non mi avrebbe dato O (log n) tempo ...

EDIT: Macchine struttura dovrebbe essere anche facile da modificare, cioè dovrebbe essere possibile sostituire l'elemento trovato con quello dato e ripetere la ricerca di un'altra M (tutto - a parte la pre-elaborazione - O (logn)). E ovviamente sarebbe bello, se potessi cambiare 'prima maggiore' a 'prima più piccola' e non dovessi cambiare troppo nell'algoritmo. E se aiuta, possiamo assumere che tutti i numeri siano positivi e non ci siano ripetizioni.

Answer 1

Creare un secondo array (lascia che sia aux) dove per ogni elemento i: aux[i] = max { arr[0],arr[1], ... ,arr[i]} (il massimo di tutti gli elementi con indice j <= i dell'array originale).

È facile vedere che questo array è ordinato per natura e un semplice binary search su aux produrrà l'indice necessario. (È facile ottenere con una ricerca binaria il primo elemento che è maggiore dell'elemento richiesto se l'elemento non esiste).

La complessità temporale è O(n) pre-elaborazione (eseguita una sola volta) e O(logn) per query.