dividere un elenco collegato in 2 liste pari contenenti i numeri più piccoli e più grandi

Question

Dato un elenco collegato di numeri interi in ordine casuale, suddividerlo in due nuovi elenchi collegati in modo tale che la differenza nella somma degli elementi di ciascuna lista sia massima e la lunghezza degli elenchi differisce di non più di 1 (nel caso in cui l'elenco originale abbia un numero dispari di elementi). Non posso presumere che i numeri nella lista siano unici.

L'algoritmo ho pensato è stato quello di fare un merge sort sulla lista collegata originale (O (n & middot; log n) tempo, O (n) spazio) e quindi utilizzare una funzione ricorsiva per raggiungere a piedi la fine della lista per determinare la sua lunghezza, facendo la divisione mentre la funzione ricorsiva si srotola. La funzione ricorsiva è O (n) e lo spazio O (n).

Questa è la soluzione ottimale? Posso pubblicare il mio codice se qualcuno pensa che sia rilevante.

Answer 1

No, non è ottimale; potete trovare lo median of a list in O(n), quindi inserirne la metà in una lista (minore della mediana o uguale, fino alla dimensione della lista essere n/2) e metà di quella in un'altra lista ((n + 1)/2). La loro differenza somma viene massimizzata, e non v'è alcuna necessità di ordinare (O (n & middot;. Log (n)) Tutte le cose saranno fatte in O (n) (spazio e tempo)

Answer 2

Perché. hai bisogno di una funzione ricorsiva? Mentre leggi l'elenco di ordinamento, puoi contare gli elementi, quindi dividili a metà.Questo elimina il fabbisogno di spazio O. n.

Anche se non è possibile contare la lunghezza dell'elenco durante l'ordinamento, è comunque possibile essere diviso in O (n) tempo e O (1) spazio: ottenere due elenchi di iteratori all'inizio, avanzare i primi 2 elementi per ogni passaggio, secondo 1 elemento per ogni passo Quando si raggiunge per la prima volta l'elenco - tagliare al secondo