Sort Colors
Bạn nhận được một mảng nums, trong đó mỗi giá trị là 0, 1 hoặc 2, tương ứng với ba màu như đỏ, trắng và xanh dương. Hãy sắp xếp lại mảng sao cho tất cả số 0 đứng trước, tiếp theo là tất cả số 1, rồi đến tất cả số 2, sau đó trả về mảng. Hãy giải bài này mà không dùng hàm sắp xếp của thư viện.
Hàm
- numsinteger-array
- các màu sắc, mỗi màu có giá trị 0, 1 hoặc 2
- Trả vềinteger-array
- các giá trị giống nhau, với tất cả số 0 trước, rồi đến tất cả số 1, sau đó là tất cả số 2
Ràng buộc
1 ≤ nums.length ≤ 1.5 × 104- Mỗi
nums[i]đều là0,1hoặc2. - Có thể thiếu một màu, và mảng có thể chỉ chứa một màu.
Ví dụ
- Đầu vào
- nums = [2, 1, 0, 2, 0, 1, 1]
- Đầu ra
- [0, 0, 1, 1, 1, 2, 2]
- Giải thích
- Mảng chứa hai số 0, ba số 1 và hai số 2, vì vậy kết quả đúng như vậy: hai số 0, tiếp theo là ba số 1, rồi đến hai số 2.
- Đầu vào
- nums = [2, 0, 2]
- Đầu ra
- [0, 2, 2]
- Giải thích
- Hoàn toàn không có số 1 nào. Số 0 duy nhất chuyển lên đầu, theo sau là hai số 2.
- Đầu vào
- nums = [1]
- Đầu ra
- [1]
- Giải thích
- Một giá trị đã đúng thứ tự, nên mảng được trả về không thay đổi.
Câu hỏi mở rộng
Nếu có k màu thay vì ba màu, với k nhỏ hơn nhiều so với độ dài của mảng, bạn sẽ thay đổi điều gì?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Chỉ có ba giá trị khác nhau có thể xuất hiện. Điều đó giúp bạn làm được gì mà cách sắp xếp tổng quát không làm được?
Đếm các số 0, 1 và 2 rồi viết lại mảng cần hai lượt duyệt. Với một lượt duyệt, hãy hình dung ba vùng cùng mở rộng: các số 0 ở đầu, các số 2 ở cuối, các số 1 ở giữa.
Giữ ba chỉ số:
low,midvàhigh. Đọcnums[mid]: nếu là 0 thì đổi chỗ vớilow, nếu là 2 thì đổi chỗ vớihigh, còn nếu là 1 thì giữ nguyên. Sau khi đổi chỗ vớihigh, hãy đọc lại cùng vị trí đó.
Lời giải
Chỉ có thể xuất hiện 0, 1 và 2, nên bạn có thể đếm chúng rồi viết lại mảng trong hai lượt. Ba con trỏ đánh dấu vị trí kết thúc của các số 0 và vị trí bắt đầu của các số 2 sẽ giúp bạn làm việc đó trong một lượt, đồng thời đặt mỗi giá trị vào đúng vị trí khi đọc. Cách phân vùng đó là thuật toán cờ quốc gia Hà Lan.
Sắp xếp nổi bọt bằng tay
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Khi không dùng hàm sắp xếp trong thư viện, cách cơ bản là tự viết hàm sắp xếp. Bubble sort duyệt qua mảng và hoán đổi hai phần tử liền kề nếu chúng không đúng thứ tự. Mỗi lượt duyệt đưa giá trị lớn nhất gặp được đến cuối, nên sau n-1 lượt, mọi vị trí đều đã cố định.
Thuật toán thực hiện khoảng n²/2 phép so sánh: hơn 10^8 phép so sánh khi n = 1.5 × 10^4, và không phép so sánh nào tận dụng việc chỉ có ba giá trị.
Thuật toán
- Chạy n-1 lượt qua mảng.
- Trong mỗi lượt, so sánh mọi cặp phần tử kề nhau
nums[j]vànums[j + 1]chưa ở vị trí cuối cùng, rồi đổi chỗ chúng nếu phần tử bên trái lớn hơn. - Sau lượt thứ
done(đếm từ 0),done + 1vị trí cuối cùng đã có giá trị cuối cùng, vì vậy lượt tiếp theo dừng trước các vị trí đó. - Trả về
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 numsĐếm từng màu, rồi viết lại
Ý tưởng
Các giá trị bằng nhau có thể thay thế cho nhau, vì vậy chỉ cần quan tâm đến số lượng. Trong ví dụ đầu tiên, hai số 0, ba số 1 và hai số 2 đã xác định đáp án trước khi bạn di chuyển bất kỳ phần tử nào.
Đọc mảng một lần để đếm từng giá trị, rồi ghi đè lên mảng từ đầu: count[0] số 0, count[1] số 1, count[2] số 2. Đây là thuật toán sắp xếp đếm. Hai lượt duyệt và ba biến đếm cho độ phức tạp thời gian O(n) và độ phức tạp không gian O(1).
Thuật toán
- Tạo ba bộ đếm, tất cả đều bằng 0.
- Đọc từng giá trị và tăng bộ đếm tương ứng lên 1.
- Ghi
count[0]số 0 từ đầu, sau đó làcount[1]số 1, rồi đếncount[2]số 2. - Trả về
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 numsMột lượt duyệt với ba con trỏ (cờ quốc gia Hà Lan)
Ý tưởng
Phân chia thành ba vùng trong khi bạn đọc. Mọi phần tử trước low là 0, mọi phần tử từ low đến trước mid là 1, mọi phần tử sau high là 2, còn các phần tử từ nums[mid] đến nums[high] chưa được đọc.
Đọc nums[mid]. Giá trị 1 đã nằm đúng vùng, nên tăng mid. Giá trị 0 đổi chỗ với nums[low] và cả hai chỉ số đều tăng: giá trị chuyển đến từ low là 1, hoặc vẫn là 0 nếu chưa gặp giá trị 1 nào, nên nó đã nằm đúng chỗ. Giá trị 2 đổi chỗ với nums[high] và high giảm, nhưng mid giữ nguyên, vì giá trị chuyển đến từ high chưa được đọc.
Mỗi bước đều tăng mid hoặc giảm high, nên vòng lặp kết thúc sau n bước. Với [2, 0, 2], giá trị 2 đầu tiên đổi chỗ với giá trị cuối cùng và high giảm còn 1; chỉ số 0 vẫn giữ giá trị 2, nên giá trị này đổi chỗ với giá trị 0; sau đó giá trị 0 giữ nguyên vị trí, tạo thành [0, 2, 2].
Thuật toán
- Đặt
low = 0,mid = 0vàhighbằng chỉ số cuối cùng. - Khi
mid ≤ high, đọcnums[mid]. - Nếu giá trị là 0, đổi chỗ với
nums[low]rồi tănglowvàmidlên một bước. - Nếu giá trị là 1, tăng
midlên một bước. - Nếu giá trị là 2, đổi chỗ với
nums[high]rồi giảmhighmột bước. Giữ nguyênmid. - Trả về
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
Lỗi thường gặp và trường hợp biên
- Tăng
midsau khi hoán đổi vớihigh. Giá trị vừa chuyển đến vẫn chưa được đọc: với[1, 2, 0], số 2 hoán đổi với số 0, nếu bỏ qua số 0 thì kết quả là[1, 0, 2]. - Lặp khi
mid < high. Khi hai chỉ số gặp nhau, ô đó vẫn chưa được đọc: với[1, 0], vòng lặp dừng trước khi đọc số 0 và trả về[1, 0]. - Để
highgiảm xuống dưới 0 khi dùng chỉ số không dấu. Một mảng chỉ có số 2, chẳng hạn[2], khiếnhighgiảm xuống -1, gây tràn dưới với kiểuusizecủa Rust. Thay vào đó, hãy giữhighở vị trí ngay sau phần chưa đọc.
Câu hỏi thường gặp3
Bài toán quốc kỳ Hà Lan là gì?
Edsger Dijkstra đã đặt ra bài toán này: sắp xếp các vật thể có ba màu thành một hàng, gồm đỏ, trắng và xanh lam như lá cờ Hà Lan, sao cho mỗi màu nằm thành một nhóm, chỉ dùng các phép đổi chỗ trong một lượt duyệt. Bài toán Sắp xếp màu cũng tương tự, nhưng dùng các giá trị 0, 1 và 2, còn lời giải của ông là cách phân vùng bằng ba con trỏ.
Độ phức tạp thời gian và không gian của Sort Colors là bao nhiêu?
Lời giải một lượt chạy trong thời gian O(n), vì mỗi bước thu nhỏ phần chưa đọc đi một ô. Lời giải dùng thêm O(1) bộ nhớ: ba chỉ số và một giá trị tạm để hoán đổi. Counting sort có cùng giới hạn nhưng đọc mảng hai lần.
Counting sort có phải là một lời giải phù hợp cho bài toán Sort Colors không?
Giải pháp này đáp ứng giới hạn thời gian O(n) và bộ nhớ O(1), nhiều người phỏng vấn chấp nhận đây là câu trả lời đầu tiên. Tiếp theo, bạn có thể được yêu cầu tìm cách giải quyết chỉ qua một lượt duyệt. Đếm là cách phù hợp hơn khi có nhiều màu, vì thao tác phân vùng chỉ chia dữ liệu thành ba nhóm.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def sortColors(nums):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
nums = [2, 1, 0, 2, 0, 1, 1]
Đầu ra mong đợi
[0, 0, 1, 1, 1, 2, 2]