Se disponiamo di un array di tutti i numeri fino a N (N < 10), qual è il modo migliore per trovare tutti i numeri mancanti. Esempio:Trova i numeri mancanti
N = 5
1 5 3 2 3
Output: 1 5 4 2 3
Nell'ex, il numero 4 era quella perduta, e c'erano 2 3s, quindi abbiamo sostituito il primo con 4 e ora la matrice è completa - tutti i numeri fino a 5 sono lì .
Esiste un semplice algoritmo in grado di farlo?
È possibile utilizzare uno set data structure - uno per tutti i numeri fino a N, uno per i numeri effettivamente visualizzati e utilizzare una differenza predefinita.
Utilizzare inutilmente un algoritmo O (N log N) in cui O (N) è sufficiente. – kennytm
Bene, ValoisBorn ha detto un semplice algoritmo. Il tuo è migliore ma è semplice? –
Penso che uno degli algoritmi O (N) sia più semplice di quello che effettivamente capisce come funziona un set. È più semplice usare un set, ma non andrai lontano usando cose che non capisci ... – IVlad
Un modo per farlo sarebbe quello di esaminare ciascun elemento della matrice in sequenza e vedere se quell'elemento è stato visto prima in elementi che hai già controllato. Se è così, cambia quel numero con uno che non hai mai visto prima e procedi.
Consentitemi di presentarvi il mio amico Schlemiel the Painter. La scoperta di un metodo più efficiente è lasciata come una sfida per il lettore.
Questo tipo di sembra come i compiti, per favore fateci sapere se non lo è. Ti darò un piccolo suggerimento, e poi migliorerò la mia risposta se confermerai che questo non è compito.
Il mio consiglio per ora è questo: Se dovessi farlo a mano, come lo faresti? Scriveresti una lista extra di numeri di qualche tempo, leggeresti la lista (quante volte?)? ecc.
Per problemi semplici, a volte la modellazione dell'algoritmo dopo un approccio intuitivo a mano può funzionare correttamente.
assumere tutti i numeri nell'intervallo 1 ≤ x ≤ N.
Mantenere 2 matrici di dimensione N. output, used (come un array associativo). tutti a 0. inizializzare
Scan dal destra, compilare i valori per output meno che non sia used.
Controllare i valori non utilizzati e inserirli negli slot vuoti (zero) di output nell'ordine.
O (N) complessità temporale, O (N) complessità dello spazio.
Poiché N è veramente piccolo, è possibile utilizzare F [i] = k se il numero i appare k volte.
int F[10]; // make sure to initialize it to 0
for (int i = 0; i < N; ++i)
++F[ numbers[i] ];
Ora, per sostituire i duplicati, Traverse l'array numero e se il numero attuale appare più di una volta, decrementare il conteggio e sostituirla con un numero che appare 0 volte e l'incremento conteggio che di numero. Puoi mantenere questo O (N) se mantieni una lista di numeri che non appaiono affatto. Ti permetterò di capire che cosa esattamente si deve fare, dato che sembra un compito a casa.
+1 stava per rispondere allo stesso modo. –
Ecco un link che ho letto proprio oggi che potrebbe essere utile. http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
È necessario specificare il problema in modo più chiaro. Come è stata fatta la sostituzione? Diciamo che so che manca un numero. Dove lo metto nell'array?Perché hai scelto di sostituire il primo '3' con' 4' (a differenza dell'ultimo '3')? Sarebbe corretto se sostituisse l'ultimo '3' con' 4' invece? – AnT
Sarebbe utile, se la domanda di Andrey fosse esaudita. – Jagannath