Qual è il modo più veloce per trovare il primo (più piccolo) numero intero che non esiste in un dato elenco di interi non ordinati (e che è maggiore del valore più piccolo della lista)?
Il mio approccio primitivo è l'ordinamento e l'elenco, c'è un modo migliore?
Supponendo che tu intenda "intero" quando dici "numero", puoi usare un bitvector di dimensione 2 ^ n, dove n è il numero di elementi (ad esempio il tuo intervallo include numeri interi compresi tra 1 e 256, quindi puoi usare un bitvector a 256 bit o 32 byte). Quando trovi un numero intero in posizione n del tuo intervallo, imposta l'ennesimo bit.
Quando hai terminato di elencare la raccolta di numeri interi, esegui un'iterazione sui bit del tuo bitvector, cercando la posizione di qualsiasi bit impostato 0. Ora corrispondono alla posizione n dei tuoi interi mancanti.
Questo è O (2 * N), quindi O (N) e probabilmente più efficiente in termini di memoria rispetto all'ordinamento dell'intero elenco.
Se si ordina prima l'intero elenco, si garantisce il runtime nel caso peggiore. Inoltre, la scelta dell'algoritmo di ordinamento è fondamentale.
Ecco come mi avvicinerei a questo problema:
return : hai trovato la tua risposta. Ecco una visualizzazione di un tipo di heap .
Solo per essere esoterici e "intelligenti", nel caso speciale dell'array avente solo un "buco", puoi provare una soluzione basata su XOR:
Questo verrà eseguito in un tempo approssimativamente 2N simile alla soluzione bitvector, ma richiede meno spazio di memoria per ogni N > sizeof (int). Tuttavia, se l'array ha più "buchi", X sarà la "somma" XOR di tutti i buchi, che sarà difficile o impossibile da separare nei valori reali del buco. In tal caso, si ricorre ad altri metodi, come gli approcci "pivot" o "bitvector" di altre risposte.
Si potrebbe anche ricorrere a questo utilizzando qualcosa di simile al metodo pivot per ridurre ulteriormente la complessità. Riorganizzare l'array in base a un punto di rotazione (che sarà il massimo del lato sinistro e il minimo del lato destro, sarà banale trovare il massimo e il minimo dell'array completo durante la rotazione). Se il lato sinistro del perno ha uno o più fori, ricorri solo in quel lato; altrimenti recita dall'altra parte. In qualsiasi punto in cui è possibile determinare che esiste un solo foro, utilizzare il metodo XOR per trovarlo (che dovrebbe essere più economico in generale che continuare a ruotare fino a un insieme di due elementi con un foro noto, che è il caso base per l'algoritmo pivot puro).
Qual è la gamma di numeri che incontrerai? Se quell'intervallo non è molto grande, è possibile risolverlo con due scansioni (tempo lineare O (n)) usando un array con tanti elementi quanti ne hai, scambiando spazio per il tempo. È possibile trovare la gamma dinamicamente con un'altra scansione. Per ridurre lo spazio, è possibile assegnare 1 bit a ciascun numero, fornendo 8 numeri di memoria per byte.
La tua altra opzione che potrebbe essere migliore per gli scenari iniziali e sarebbe al posto di copiare la memoria è modificare l'ordinamento di selezione per uscire presto se il min trovato in un passaggio di scansione non è 1 più dell'ultimo min trovato.
No, non proprio. Dal momento che qualsiasi numero non ancora analizzato potrebbe sempre essere uno che riempie un determinato "buco", non è possibile evitare di scansionare ogni numero almeno una volta e quindi confrontarlo con i possibili vicini. Probabilmente potresti accelerare le cose costruendo un albero binario o giù di lì e poi attraversarlo da sinistra a destra fino a trovare un buco, ma che è essenzialmente della stessa complessità temporale dell'ordinamento, poiché è l'ordinamento. E probabilmente non ti verrà in mente niente di più veloce di Timsort .
La maggior parte delle idee qui non sono altro che un semplice ordinamento. La versione bitvector è semplice Bucketsort. È stato anche menzionato il tipo di heap. In pratica, si riduce a scegliere l'algoritmo di ordinamento corretto che dipende dai requisiti di tempo / spazio e anche dall'intervallo e dal numero di elementi.
Dal mio punto di vista, l'uso di una struttura ad heap è probabilmente la soluzione più generale (un heap fornisce in pratica gli elementi più piccoli in modo efficiente senza un ordinamento completo).
Potresti anche analizzare approcci che trovano prima i numeri più piccoli e poi scansionare per ogni numero più grande di quello. Oppure trovi i 5 numeri più piccoli sperando che il testamento abbia un gap.
Tutti questi algoritmi hanno la loro forza in base alle caratteristiche di input e ai requisiti del programma.
Una soluzione che non utilizza spazio di archiviazione aggiuntivo o presuppone la larghezza (32 bit) degli interi.
In un passaggio lineare trova il numero più piccolo. Chiamiamo questo "min". O (n) complessità temporale.
Scegli un elemento di pivot casuale e crea una partizione di stile Quicksort.
Se il pivot è finito nella posizione = ("pivot" - "min"), quindi recurse sul lato destro della partizione, altrimenti recurse sul lato sinistro della partizione. L'idea è che se non ci sono buchi dall'inizio, il perno si troverà in posizione "(pivot" - "min"), quindi il primo foro dovrebbe trovarsi a destra della partizione e viceversa.
Il caso base è un array di 1 elemento e il buco si trova tra questo elemento e il successivo.
La complessità del tempo di esecuzione totale prevista è O (n) (8 * n con le costanti) e il caso peggiore è O (n ^ 2). L'analisi della complessità temporale per un problema simile può essere trovata qui .
Credo di aver trovato qualcosa che dovrebbe funzionare in modo generale ed efficiente se si è certi di non avere duplicati * (tuttavia, dovrebbe essere estensibile a qualsiasi numero di fori e qualsiasi intervallo di numeri interi).
L'idea alla base di questo metodo è come quicksort, in quanto troviamo un pivot e una partizione attorno ad esso, quindi recidiamo sul lato (i) con un buco. Per vedere quali lati hanno il foro, troviamo i numeri più bassi e più alti e confrontali con il perno e il numero di valori su quel lato. Supponiamo che il pivot sia 17 e che il numero minimo sia 11. Se non ci sono buchi, dovrebbero esserci 6 numeri (11, 12, 13, 14, 15, 16, 17). Se ci sono 5, sappiamo che c'è un buco su quel lato e possiamo ricorrere solo da quella parte per trovarlo. Ho difficoltà a spiegarlo in modo più chiaro, quindi prendiamo un esempio.
15 21 10 13 18 16 22 23 24 20 17 11 25 12 14
Pivot:
10 13 11 12 14 |15| 21 18 16 22 23 24 20 17 25
15 è il pivot, indicato da pipe ( || ). Ci sono 5 numeri sul lato sinistro del perno, come dovrebbe essere (15 - 10) e 9 sulla destra, dove dovrebbero esserci 10 (25 - 15). Quindi recitiamo dalla parte giusta; noteremo che il limite precedente era 15 nel caso in cui il foro fosse adiacente ad esso (16).
[15] 18 16 17 20 |21| 22 23 24 25
Ora ci sono 4 numeri sul lato sinistro ma dovrebbero esserci 5 (21 - 16). Quindi ci rechiamo lì, e di nuovo noteremo il limite precedente (tra parentesi).
[15] 16 17 |18| 20 [21]
La parte sinistra ha i 2 numeri corretti (18 - 16), ma la destra ha 1 invece di 2 (20 - 18). A seconda delle condizioni finali, potremmo confrontare il numero 1 con i due lati (18, 20) e vedere che 19 manca o recita ancora una volta:
[18] |20| [21]
Il lato sinistro ha una dimensione pari a zero, con uno spazio tra il perno (20) e il limite precedente (18), quindi 19 è il foro.
*: Se ci sono duplicati, potresti probabilmente usare un hash set per rimuoverli in tempo O (N), mantenendo il metodo generale O (N), ma che potrebbe richiedere più tempo di usando un altro metodo.
Leggi altre domande sui tag numbers algorithms list search