Sort Colors
Otrzymujesz tablicę nums, w której każda wartość to 0, 1 lub 2: trzy kolory, takie jak czerwony, biały i niebieski. Zmień kolejność elementów tablicy tak, aby najpierw znalazły się wszystkie 0, potem wszystkie 1, a na końcu wszystkie 2, i zwróć ją. Rozwiąż to bez użycia bibliotecznej funkcji sortującej.
Funkcja
- numsinteger-array
- kolory, każdy o wartości 0, 1 lub 2
- Zwracainteger-array
- te same wartości, najpierw wszystkie 0, potem wszystkie 1, a następnie wszystkie 2
Ograniczenia
1 ≤ nums.length ≤ 1.5 × 104- Każde
nums[i]to0,1lub2. - Może brakować koloru, a tablica może zawierać jeden kolor.
Przykłady
- Wejście
- nums = [2, 1, 0, 2, 0, 1, 1]
- Wyjście
- [0, 0, 1, 1, 1, 2, 2]
- Wyjaśnienie
- Tablica zawiera dwie 0, trzy 1 i dwie 2, więc wynik jest dokładnie taki: dwie 0, potem trzy 1, a następnie dwie 2.
- Wejście
- nums = [2, 0, 2]
- Wyjście
- [0, 2, 2]
- Wyjaśnienie
- W ogóle nie ma 1. Pojedyncze 0 przesuwa się na początek, a dwie 2 podążają za nim.
- Wejście
- nums = [1]
- Wyjście
- [1]
- Wyjaśnienie
- Pojedyncza wartość jest już w odpowiedniej kolejności, więc tablica wraca bez zmian.
Pytanie dodatkowe
Co należałoby zmienić, gdyby było k kolorów zamiast trzech, a k było dużo mniejsze od długości tablicy?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Mogą pojawić się tylko trzy różne wartości. Co możesz dzięki temu zrobić, czego nie da się zrobić za pomocą ogólnego sortowania?
Policzenie zer, jedynek i dwójek oraz przepisanie tablicy odbywa się w dwóch przebiegach. W jednym przebiegu wyobraź sobie, że trzy obszary rosną jednocześnie: zera z przodu, dwójki z tyłu, a jedynki pomiędzy nimi.
Utrzymuj trzy indeksy:
low,midihigh. Odczytajnums[mid]: 0 zamień z elementem pod indeksemlow, 2 zamień z elementem pod indeksemhigh, a 1 pozostaw. Po zamianie z elementem pod indeksemhighodczytaj ponownie tę samą pozycję.
Rozwiązanie
Mogą pojawić się tylko 0, 1 i 2, więc możesz je policzyć i przepisać tablicę w dwóch przebiegach. Trzy wskaźniki, które wskazują, gdzie kończą się 0 i gdzie zaczynają się 2, pozwalają zrobić to w jednym przebiegu, umieszczając każdą wartość na swoim miejscu podczas odczytywania. Ten podział to algorytm flagi narodowej Holandii.
Sortowanie bąbelkowe ręcznie
Poprawne, ale nie kończy się na największych testach
Intuicja
Bez sortowania za pomocą biblioteki punktem odniesienia jest sortowanie, które napiszesz samodzielnie. Sortowanie bąbelkowe przechodzi po tablicy i zamienia miejscami sąsiadujące elementy, które są w niewłaściwej kolejności. W każdym przebiegu przenosi największą napotkaną wartość na koniec, więc po n-1 przebiegach każda pozycja jest już na swoim miejscu.
Wykonuje około n²/2 porównań: ponad 10^8 dla n = 1.5 × 10^4, a żadne z nich nie wykorzystuje faktu, że istnieją tylko trzy wartości.
Algorytm
- Wykonaj n-1 przebiegów po tablicy.
- W każdym przebiegu porównaj każdą parę sąsiadujących elementów
nums[j]inums[j + 1], które nie są jeszcze na końcowych pozycjach, i zamień je miejscami, gdy lewy element jest większy. - Po przebiegu o numerze
done(licząc od 0) ostatniedone + 1pozycje zawierają już swoje końcowe wartości, więc następny przebieg kończy się przed nimi. - Zwróć
nums.
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return numsPolicz każdy kolor, a następnie przepisz
Intuicja
Równe wartości można stosować zamiennie, więc liczą się tylko ich liczby. W pierwszym przykładzie dwie 0, trzy 1 i dwie 2 ustalają odpowiedź, zanim cokolwiek przesuniesz.
Przejdź raz po tablicy, aby policzyć każdą wartość, a następnie nadpisz ją od początku: count[0] zer, count[1] jedynek, count[2] dwójek. To sortowanie przez zliczanie. Dwa przebiegi i trzy liczniki zapewniają czas O(n) i przestrzeń O(1).
Algorytm
- Utwórz trzy liczniki, wszystkie równe 0.
- Odczytaj każdą wartość i dodaj jeden do jej licznika.
- Zapisz od początku
count[0]zer, następniecount[1]jedynek, a potemcount[2]dwójek. - Zwróć
nums.
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return numsJedno przejście z trzema wskaźnikami (holenderska flaga narodowa)
Intuicja
Utwórz trzy regiony podczas czytania. Wszystko przed low to 0, wszystko od low do, ale bez mid, to 1, wszystko za high to 2, a nums[mid] do nums[high] jest nieprzeczytane.
Odczytaj nums[mid]. 1 jest już w swoim regionie, więc przesuń mid dalej. 0 zamienia się miejscami z nums[low] i oba indeksy przesuwają się dalej: wartość, która wraca z low, to 1 albo ta sama 0, jeśli nie napotkano jeszcze żadnej 1, więc jest na swoim miejscu. 2 zamienia się miejscami z nums[high], a high cofa się, ale mid pozostaje bez zmian, ponieważ wartość, która przyszła z high, jest nieprzeczytana.
Każdy krok przesuwa mid do przodu lub high do tyłu, więc pętla kończy się po n krokach. Dla [2, 0, 2] pierwsza 2 zamienia się miejscami z ostatnią, a high zmniejsza się do 1; indeks 0 nadal zawiera 2, która zamienia się miejscami z 0; 0 pozostaje na miejscu, dając [0, 2, 2].
Algorytm
- Ustaw
low = 0,mid = 0, ahighna ostatni indeks. - Gdy
mid ≤ high, odczytajnums[mid]. - Jeśli wynosi 0, zamień ją z
nums[low]i przesuńloworazmido jeden krok w prawo. - Jeśli wynosi 1, przesuń
mido jeden krok w prawo. - Jeśli wynosi 2, zamień ją z
nums[high]i przesuńhigho jeden krok w lewo. Pozostawmidna miejscu. - Zwróć
nums.
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
Pułapki i przypadki brzegowe
- Przesuwanie
middo przodu po zamianie zhigh. Wartość, która trafia na to miejsce, jest nieodczytana: dla[1, 2, 0]wartość 2 zamienia się z 0, a pominięcie 0 zwraca[1, 0, 2]. - Kontynuowanie pętli, dopóki
mid < high. Gdy oba indeksy się spotkają, ta komórka nadal jest nieodczytana: dla[1, 0]pętla zatrzymuje się, zanim odczyta 0, i zwraca[1, 0]. - Dopuszczenie, by
highspadło poniżej zera przy użyciu indeksu bez znaku. Tablica zawierająca tylko 2, na przykład[2], powoduje, żehighprzyjmuje wartość -1, co prowadzi do przepełnienia typuusizew Rust. Zamiast tego utrzymujhigho jedną pozycję za nieodczytaną częścią.
Najczęstsze pytania3
Na czym polega problem flagi Holandii?
Edsger Dijkstra postawił problem: ułóż w rzędzie obiekty w trzech kolorach — czerwonym, białym i niebieskim, jak na fladze Holandii — tak, aby każdy kolor był zgrupowany, wykonując jeden przebieg i używając wyłącznie zamian. Sortowanie kolorów to ten sam problem z wartościami 0, 1 i 2, a jego rozwiązaniem jest podział z użyciem trzech wskaźników.
Jaka jest złożoność czasowa i pamięciowa problemu Sort Colors?
Rozwiązanie jednokrotnego przejścia działa w czasie O(n), ponieważ każdy krok zmniejsza nieodczytaną część o jedną komórkę. Wykorzystuje O(1) dodatkowej pamięci: trzy indeksy i wartość tymczasową do zamiany. Sortowanie przez zliczanie ma takie same ograniczenia, ale odczytuje tablicę dwukrotnie.
Czy sortowanie przez zliczanie jest akceptowalną odpowiedzią na zadanie Sort Colors?
Spełnia ograniczenia czasowe O(n) i pamięciowe O(1), a wielu rekruterów akceptuje takie rozwiązanie jako pierwszą odpowiedź. Następnie spodziewaj się prośby o rozwiązanie w jednym przebiegu. Zliczanie jest lepszym narzędziem, gdy jest wiele kolorów, ponieważ podział tworzy tylko trzy grupy.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def sortColors(nums):
# Wpisz kod tutajTest #1
Test #2
Test #3
Argument
nums = [2, 1, 0, 2, 0, 1, 1]
Oczekiwany wynik
[0, 0, 1, 1, 1, 2, 2]