Sto lavorando a un problema di compiti a casa e sto riscontrando alcune difficoltà nella creazione di una soluzione O (n * logn). Devo scrivere una funzione che accetta una matrice pre-ordinata e un valore da cercare. Quindi ho bisogno di trovare se due elementi della somma dell'array equivalgono a quel valore.Determinazione della somma di due elementi in una somma di matrice preordinata uguale a un determinato valore
Ho bisogno di creare algoritmi O (n) e O (n * logn) per questo.
O (n) è stato facile da creare; tuttavia, ho difficoltà a creare l'algoritmo O (n * logn) senza aggiungere del codice gratuito che non aiuti effettivamente a risolvere il problema. Se qualcuno potesse darmi qualche suggerimento su cosa potrei mancare sarebbe apprezzato.
Come hai fatto in O (n) ?? – letsc
@letsc: utilizza due indici aeb; inizializza con a = 1 eb = n. Controlla la somma degli elementi agli indici a e b. Se la somma è il tuo obiettivo, fermati, hai trovato gli elementi. Se la somma è inferiore, aumenta a; se è inferiore, diminuisci b. Quando a = b, stop, non ci sono elementi corrispondenti. Poiché gli elementi sono ordinati, salterai solo le coppie che sai non sono candidate. – Joubarc