podzieli listę połączoną na dwie równe listy zawierające najmniejsze i największe liczby

Biorąc pod uwagę połączoną listę liczb całkowitych w losowej kolejności, podziel ją na dwie nowe połączone listy tak, aby różnica w sumie elementów każdej listy była maksymalna, a długość list różni się o nie więcej niż 1 (w przypadku, gdy pierwotna lista zawiera nieparzystą liczbę elementów). Nie mogę założyć, że liczby na liście są unikalne.podzieli listę połączoną na dwie równe listy zawierające najmniejsze i największe liczby

Algorytm myślałem żeby zrobić coś w rodzaju scalania na pierwotnej liście połączonej (O (n & middot; log n) czas, O (n) kosmiczny), a następnie użyć funkcji rekurencyjnej chodzić do koniec listy, aby określić jej długość, wykonując podział w trakcie rozwijania funkcji rekursywnej. Funkcja rekursywna to O (n) czasu i O (n) przestrzeni.

Czy to jest optymalne rozwiązanie? Mogę opublikować mój kod, jeśli ktoś uważa, że jest to istotne.

Źródło

2011-02-09 Robert S. Barnes

Jeżeli twój Implementacja listy powiązanej zachowuje właściwość wielkości, a następnie musisz przejść tylko połowę listy, aby podzielić ją na pół. (Może chcieć sprawdzić http://codereview.stackexchange.com!) – Jeremy

@Jeremy Heiler: Brak właściwości rozmiaru, tylko bardzo prosta podstawowa lista połączona z jane, naprawdę nic więcej niż kilka połączonych ze sobą węzłów. –

Jeśli twój egzamin nie wymaga wdrożenia sortowania, możesz również użyć Collections.sort do sortowania. – karakuricoder

Nie, to nie jest optymalne; możesz znaleźć median of a list in O(n), a następnie umieścić połowę z nich na jednej liście (mniejszej niż mediana lub równej, do rozmiaru listy to n/2), a połowę z nich na innej liście ((n + 1)/2). Ich różnica suma jest zmaksymalizowane, i nie ma potrzeby, aby sortować (O (n & middot;. Log (n)) Wszystkie rzeczy zostaną wykonane w O (n) (przestrzeń i czas)

Źródło

2011-02-09 13:23:21

Podany link wydaje się wskazywać, że ten algorytm jest odpowiedni dla macierzy dostępu losowego. Czy na pewno działa to na połączonych listach? –

@Robert S. Barnes: Jeśli to konieczne, możemy skopiować listę najpierw do tablicy, a później z powrotem, wciąż O (n). –

Jeszcze jedna rzecz, oparta na tej analizie http://www.soe.ucsc.edu/classes/cmps102/Spring05/selectAnalysis.pdf algorytmu Median of Medians, wymaga, aby elementy w tablicy były unikalne. Nie mogę tego założyć. –

Dlaczego robić. potrzebujesz funkcji rekursywnej? Podczas sortowania listy możesz liczyć jej elementy, a następnie podzielić je na pół To zmniejsza zapotrzebowanie na miejsce O (n)

Nawet jeśli nie możesz liczyć długości listy podczas sortowania, nadal możesz Podziel się w O (n) czasie i O (1) spacji: pobierz dwa iteratory list na początku, przesuń najpierw dwa elementy na każdym kroku, drugi po jednym elemencie, po pierwszym dotarciu do końca listy - obcięcie w drugim kroku:

Źródło

2011-02-09 13:24:32 blaze

I już dzieliłem w czasie O (n). Zajmuje przestrzeń O (n), ponieważ robię kopie oryginalnej LL. –

podzieli listę połączoną na dwie równe listy zawierające najmniejsze i największe liczby

Odpowiedz

Powiązane problemy