Sort Colors
Kamu mendapatkan sebuah array nums yang setiap nilainya adalah 0, 1, atau 2: tiga warna, seperti merah, putih, dan biru. Susun ulang array tersebut agar semua angka 0 berada di awal, lalu semua angka 1, kemudian semua angka 2, dan kembalikan array tersebut. Selesaikan tanpa fungsi pengurutan dari library.
Fungsi
- numsinteger-array
- warnanya, masing-masing bernilai 0, 1, atau 2
- Mengembalikaninteger-array
- nilai yang sama dengan semua 0 terlebih dahulu, lalu semua 1, kemudian semua 2
Batasan
1 ≤ nums.length ≤ 1.5 × 104- Setiap
nums[i]bernilai0,1atau2. - Satu warna mungkin tidak ada, dan array mungkin hanya berisi satu warna.
Contoh
- Input
- nums = [2, 1, 0, 2, 0, 1, 1]
- Output
- [0, 0, 1, 1, 1, 2, 2]
- Penjelasan
- array tersebut berisi dua angka 0, tiga angka 1, dan dua angka 2, jadi hasilnya persis seperti itu: dua angka 0, lalu tiga angka 1, lalu dua angka 2.
- Input
- nums = [2, 0, 2]
- Output
- [0, 2, 2]
- Penjelasan
- Tidak ada angka 1 sama sekali. Satu angka 0 berpindah ke depan dan dua angka 2 mengikutinya.
- Input
- nums = [1]
- Output
- [1]
- Penjelasan
- Satu nilai sudah berurutan, jadi array tetap sama.
Pertanyaan lanjutan
Apa yang akan kamu ubah jika ada k warna, bukan tiga, dengan k jauh lebih kecil daripada panjang array?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Hanya tiga nilai berbeda yang dapat muncul. Apa yang bisa kamu lakukan dengan itu yang tidak bisa dilakukan oleh pengurutan umum?
Menghitung angka 0, 1, dan 2 lalu menyusun ulang array dilakukan dalam dua kali lintasan. Untuk satu lintasan, bayangkan tiga wilayah yang tumbuh secara bersamaan: angka 0 di depan, angka 2 di belakang, dan angka 1 di antaranya.
Pertahankan tiga indeks:
low,mid, danhigh. Bacanums[mid]: nilai 0 ditukar kelow, nilai 2 ditukar kehigh, nilai 1 tetap. Setelah ditukar denganhigh, baca kembali posisi yang sama.
Solusi
Hanya 0, 1, dan 2 yang bisa muncul, jadi kamu bisa menghitungnya lalu menulis ulang array dalam dua lintasan. Tiga penunjuk yang menandai batas akhir 0 dan awal 2 melakukannya dalam satu lintasan, dengan menempatkan setiap nilai di tempatnya saat kamu membacanya. Partisi itu adalah algoritma bendera nasional Belanda.
Urutkan dengan bubble sort secara manual
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Tanpa sort dari library, pilihannya adalah sort yang kamu tulis sendiri. Bubble sort menelusuri array dan menukar dua elemen bertetangga yang urutannya salah. Setiap lintasan membawa nilai terbesar yang ditemuinya ke bagian akhir, jadi setelah n-1 lintasan, setiap posisi sudah tetap.
Bubble sort melakukan sekitar n²/2 perbandingan: lebih dari 10^8 untuk n = 1.5 × 10^4, dan tidak satu pun perbandingan itu memanfaatkan fakta bahwa hanya ada tiga nilai.
Algoritma
- Jalankan n-1 lintasan pada array.
- Pada setiap lintasan, bandingkan setiap pasangan elemen bertetangga
nums[j]dannums[j + 1]yang belum berada di posisi akhir, lalu tukar keduanya jika elemen di kiri lebih besar. - Setelah lintasan bernomor
done(dihitung mulai dari 0), posisi terakhir sebanyakdone + 1berisi nilai akhirnya, jadi lintasan berikutnya berhenti sebelum posisi tersebut. - Kembalikan
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 numsHitung setiap warna, lalu tulis ulang
Intuisi
Nilai yang sama dapat saling menggantikan, jadi hanya jumlahnya yang penting. Pada contoh pertama, dua angka 0, tiga angka 1, dan dua angka 2 menentukan jawaban sebelum kamu memindahkan apa pun.
Baca array sekali untuk menghitung setiap nilai, lalu timpa array mulai dari awal: count[0] angka nol, count[1] angka satu, count[2] angka dua. Ini adalah pengurutan dengan penghitungan. Dua kali pemrosesan dan tiga penghitung menghasilkan waktu O(n) dan ruang O(1).
Algoritma
- Buat tiga penghitung, semuanya bernilai 0.
- Baca setiap nilai dan tambahkan satu ke penghitungan yang sesuai.
- Tulis
count[0]angka nol dari awal, lalucount[1]angka satu, kemudiancount[2]angka dua. - Kembalikan
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 numsSatu kali lintasan dengan tiga pointer (bendera nasional Belanda)
Intuisi
Kembangkan tiga wilayah sambil membaca. Semua yang berada sebelum low adalah 0, semua yang dimulai dari low hingga sebelum mid adalah 1, semua yang berada setelah high adalah 2, dan nums[mid] hingga nums[high] belum dibaca.
Baca nums[mid]. Nilai 1 sudah berada di wilayahnya, jadi lanjutkan mid. Nilai 0 ditukar dengan nums[low] dan keduanya bergerak maju: nilai yang kembali dari low adalah 1, atau 0 yang sama jika belum ada 1 yang ditemukan, jadi nilainya sudah berada di tempat yang tepat. Nilai 2 ditukar dengan nums[high] dan high bergerak mundur, tetapi mid tetap, karena nilai yang berasal dari high belum dibaca.
Setiap langkah memajukan mid atau memundurkan high, jadi perulangan berakhir setelah n langkah. Pada [2, 0, 2], nilai 2 pertama ditukar dengan nilai terakhir dan high turun menjadi 1; indeks 0 masih berisi nilai 2, yang ditukar dengan nilai 0; lalu nilai 0 tetap di tempatnya, sehingga hasilnya [0, 2, 2].
Algoritma
- Tetapkan
low = 0,mid = 0, danhighke indeks terakhir. - Selama
mid ≤ high, bacanums[mid]. - Jika nilainya 0, tukar dengan
nums[low], lalu geserlowdanmidsatu langkah ke kanan. - Jika nilainya 1, geser
midsatu langkah ke kanan. - Jika nilainya 2, tukar dengan
nums[high], lalu geserhighsatu langkah ke kiri. Biarkanmidtetap di tempat. - Kembalikan
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
Jebakan dan kasus tepi
- Memajukan
midsetelah pertukaran denganhigh. Nilai yang tiba belum dibaca: pada[1, 2, 0], angka 2 bertukar tempat dengan angka 0, dan melewati angka 0 menghasilkan[1, 0, 2]. - Melakukan perulangan selama
mid < high. Saat keduanya bertemu, elemen tersebut masih belum dibaca: pada[1, 0], perulangan berhenti sebelum membaca angka 0 dan menghasilkan[1, 0]. - Membiarkan
highturun di bawah nol dengan indeks unsigned. array yang hanya berisi angka 2, seperti[2], membuathighmenjadi -1, yang menyebabkan underflow padausizedi Rust. Sebaliknya, pertahankanhighsatu posisi setelah bagian yang belum dibaca.
Pertanyaan yang sering diajukan3
Apa itu masalah bendera nasional Belanda?
Edsger Dijkstra mengajukan masalah ini: susun objek dalam tiga warna secara berderet, yaitu merah, putih, dan biru seperti bendera Belanda, sehingga setiap warna berkelompok, dalam satu kali lintasan dengan hanya menggunakan pertukaran. Sort Colors adalah masalah yang sama dengan 0, 1, dan 2, dan solusinya adalah partisi tiga pointer.
Apa kompleksitas waktu dan ruang dari Sort Colors?
Solusi satu lintasan berjalan dalam waktu O(n), karena setiap langkah memperkecil bagian yang belum dibaca sebanyak satu sel. Solusi ini menggunakan ruang tambahan O(1): tiga indeks dan satu nilai sementara untuk pertukaran. Counting sort memiliki batas yang sama, tetapi membaca array dua kali.
Apa counting sort merupakan jawaban yang dapat diterima untuk Sort Colors?
Solusi ini memenuhi batas waktu O(n) dan ruang O(1), dan banyak pewawancara menerimanya sebagai jawaban pertama. Bersiaplah untuk diminta melakukan satu kali penelusuran pada langkah berikutnya. Penghitungan adalah cara yang lebih baik saat ada banyak warna, karena partisi hanya membagi elemen menjadi tiga kelompok.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def sortColors(nums):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [2, 1, 0, 2, 0, 1, 1]
Output yang diharapkan
[0, 0, 1, 1, 1, 2, 2]