Questa è una domanda di intervista. Dato un array intero ordinato e il numero z trova tutte le coppie (x, y) nella matrice in modo che x + y < z. Può essere fatto meglio di O (n^2)?Trova tutte le coppie (x, y) in una matrice ordinata in modo che x + y <z
P.S. So che possiamo trovare tutte le coppie (x, y | x + y == z) in O (N).
Non si può necessariamente trovare tutte queste coppie in O (n) tempo, perché ci potrebbero essere O (n) coppie di valori che hanno questa proprietà. In generale, un algoritmo non può impiegare meno tempo per essere eseguito rispetto al numero di valori che produce.
Spero che questo aiuti!
In genera, no non può. Considerare il caso in cui x + y < z per tutti x, nella matrice. È necessario toccare (ad es. Visualizzare) tutte le coppie possibili nel set n(n - 1)/2. Questo è fondamentalmente O (n^2).
È possibile trovare in O (N), se si aggiunge il vincolo aggiuntivo che ciascun elemento è univoco.
Dopo aver trovato tutte le coppie x + y == z, si sa che per ogni x e y che soddisfa tale condizione, ogni x o y (scegline uno) che si trova ad un indice inferiore rispetto alla sua coppia soddisfa la x + y < z condizioni.
In realtà, la selezione di questi e la loro uscita richiederebbe O (n^2), ma in un certo senso, le coppie x + y == z sono una forma compressa della risposta, insieme all'input.
(È possibile preelaborare l'input in un modulo in cui ogni elemento è univoco, insieme a un contatore per il numero di occorrenze. Ciò richiederebbe il tempo O (N). È possibile generalizzare questa soluzione agli array non ordinati, aumentando il tempo di O (nlogn).)
La giustificazione per dire che trovare le coppie in un tempo linearmente proporzionale alla dimensione della soluzione: Supponiamo che la domanda sia "quali sono gli interi tra 0 e l'ingresso dato K" ?
Se viene richiesto di emettere tutte le coppie che soddisfano tale proprietà, non penso che ci sia qualcosa di meglio di O (N^2) poiché ci possono essere coppie O (N^2) nell'output.
Ma questo vale anche per x + y = z, per il quale si afferma che esiste una soluzione O (N) - quindi potrei mancare qualcosa.
Sospetto che la domanda iniziale abbia richiesto il numero di coppie. In tal caso, può essere eseguito in O (N log (N)). Per ogni elemento x scopri y = z - x e fai una ricerca binaria per y nell'array. La posizione di y dà il numero di coppie che possono essere formate con quel particolare valore di x. Sommando questo su tutti i valori nella matrice ti dà la risposta. Ci sono valori N e trovare il numero se per ogni coppia occorrono O (log (N)) (ricerca binaria), quindi il tutto è O (N log (N)).
Perché è un ordinato array intero, è possibile utilizzare l'algoritmo di ricerca binaria , quindi la cosa migliore è O(N), e il peggio è O(N*logN), il caso medio è anche O(N*logN).
È possibile ordinare l'array e per ogni elemento minore di z, utilizzare ricerca binaria - O totale (NlogN).
Tempo di esecuzione totale: O (| P | + NlogN), dove P è le coppie risultanti.
Esiste effettivamente una soluzione O (nlogn) a questa domanda. Quello che vorrei fare (dopo aver controllato prima se sono autorizzato a farlo) è definire il formato di output del mio algoritmo/funzione.
Lo definirei come una sequenza di elementi (S, T). S - Posizione dell'elemento nell'array (o il suo valore). T - Posizione della matrice secondaria [0, T]. Ad esempio, se T = 3, significa che l'elemento S combinato con gli elementi 0,1,2 e 3 soddisfa la condizione desiderata.
Il risultato totale di questo è O (nlogn) tempo di esecuzione e O (n) memoria.
Mentre sono completamente d'accordo con la tua osservazione, vedi il mio commento riguardo alla nostra capacità di definire il "formato" di output. – ZeDuS