mi è stato chiesto questa domanda:mediana di liste
Si sono dati due elenchi di numeri interi, ciascuno dei quali è ordinato in ordine crescente e ciascuno dei quali ha lunghezza n. Tutti gli interi nei due elenchi sono diversi. Desiderate trovare l'n-esimo elemento più piccolo dell'unione delle due liste. (Cioè, se le liste concatenate e risolto la lista risultante in ordine crescente, l'elemento che sarebbe nella posizione n-esimo.)
mia soluzione: Assumiamo che le liste sono 0-indicizzati.
O (n) soluzione: Una soluzione straight-forward è osservare che gli array sono già ordinati, in modo che possiamo unire e fermata dopo n passi. Non è necessario copiare i primi elementi n-1 in un nuovo array, quindi questa soluzione impiega tempo O (n) e memoria O (1).
O (log2 n) soluzione: La soluzione O (log2 n) utilizza ricerca binaria alternata su ciascuna lista. In breve, prende l'elemento centrale nell'intervallo di ricerca corrente nel primo elenco (l1 [p1]) e lo cerca in l2. Poiché gli elementi sono unici, troveremo al massimo 2 valori più vicini a l1 [p1]. A seconda dei loro valori relativi a l1 [p1-1] e l1 [p1 + 1] e ai loro indici p21 e p22, restituiamo l'elemento n-esimo o ricorsivo: Se la somma di uno qualsiasi dei (al massimo) 3 gli indici in l1 possono essere combinati con uno (al massimo) 2 indici in l2 in modo che l1 [p1 '] e l2 [p2'] siano proprio uno accanto all'altro nell'unione ordinata delle due liste e p1 '+ p2 '= n o p1' + p2 '= n + 1, restituiamo uno dei 5 elementi. Se p1 + p2> n, si ricorre alla metà sinistra dell'intervallo di ricerca in l1, altrimenti si ricorre all'intervallo corretto. In questo modo, per i punti medi fuori da O (log n) in l1 eseguiamo una ricerca binaria O (log n) in l2. Pertanto il tempo di esecuzione è O (log2 n).
O (log n) Soluzione: Supponendo che l'liste L1 e L2 hanno tempo di accesso costante a qualsiasi dei loro elementi, abbiamo possibile utilizzare una versione modificata di ricerca binaria per ottenere un O (log n) soluzione. L'approccio più semplice è quello di cercare un indice p1 in uno solo degli elenchi e calcolare l'indice corrispondente p2 nell'altro elenco in modo che p1 + p2 = n in ogni momento. (Questo presuppone che gli elenchi siano indicizzati da 1.) Per prima cosa controlliamo il caso speciale quando tutti gli elementi di una lista sono più piccoli di qualsiasi elemento nell'altra lista: If l1 [n] < l2 [0] return l1 [n ]. Se l2 [n] < l1 [0] restituisce l2 [n]. Se non troviamo il più piccolo elemento n-esimo dopo questo passaggio, chiamare findNth (1, n) con il pseudocodice approssimativa:
findNth(start,end)
p1 = (start + end)/2
p2 = n-p1
if l1[p1] < l2[p2]:
if l1[p1 + 1] > l2[p2]:
return l2[p2]
else:
return findNth(p1+1, end)
else:
if l2[p2 + 1] > l1[p1]:
return l1[p1]
else:
return findNth(start,p1-1)
Elemento l2 [p2] viene restituito quando l2 [P2] è maggiore di esattamente p1 + p2-1 = n-1 elementi (e quindi è l'n-esima più piccola). l1 [p1] viene restituito nelle stesse condizioni simmetriche. Se l1 [p1] < l2 [p2] e l1 [p1 + 1] < l2 [p2], il grado di l2 [p2] è maggiore di n, quindi è necessario prendere più elementi da l1 e meno da l2. Pertanto cerchiamo p1 nella metà superiore dell'intervallo di ricerca precedente. D'altra parte, se l2 [p2] < l1 [p1] e l2 [p2 + 1] < l1 [p1], il grado di l1 [p1] è maggiore di n. Quindi il vero p1 si troverà nella metà inferiore del nostro attuale intervallo di ricerca. Dato che dimezziamo la dimensione del problema ad ogni chiamata a findNth e dobbiamo fare solo un lavoro costante per dimezzare la dimensione del problema, la ricorrenza di questo algoritmo è T (n) = T (n/2) + O (1), che ha una soluzione di tempo O (log n).
L'intervistatore mi chiede continuamente approcci diversi per il problema di cui sopra. Ho proposto tre approcci sopra.Sono corretti? C'è qualche altra migliore soluzione possibile per questa domanda? In realtà questa domanda ha richiesto molte volte, quindi ti preghiamo di fornire alcune informazioni utili.
cos'è n? la dimensione degli elenchi o l'ordine dell'elemento? Modifica la tua domanda per rimuovere questa ambiguità. – UmNyobe
@UmNyobe qui n è la dimensione della lista .. –
Non è una lista una struttura dati SENZA accesso casuale? Questo è ciò che li differenzia dagli array. – blaze