Cho một mảng nums gồm n đối tượng có màu đỏ (0), trắng (1) hoặc xanh (2). Hãy sắp xếp mảng in-place sao cho các đối tượng cùng màu đứng cạnh nhau theo thứ tự đỏ, trắng, xanh.
Yêu cầu: Một lần quét (One-pass) O(n) thời gian và O(1) bộ nhớ phụ, không dùng hàm sort có sẵn.
Ví dụ 1: nums = [2, 0, 2, 1, 1, 0] -> [0, 0, 1, 1, 2, 2]
Định Dạng Đầu Vào (Input)
Một dòng chứa mảng nums
Định Dạng Đầu Ra (Output)
Mảng nums sau khi sắp xếp
Ràng Buộc (Constraints)
1 <= nums.length <= 300
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[2, 0, 2, 1, 1, 0]
Output:
[0, 0, 1, 1, 2, 2]
Giải thích: Sắp xếp chuẩn 0, 1, 2
Ví dụ 2:
Input:
[2, 0, 1]
Output:
[0, 1, 2]
Giải thích: 3 phần tử
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Thuật Toán Cờ Hà Lan (Dutch National Flag) O(n)
Dùng 3 con trỏ: low = 0, mid = 0, high = n - 1:
- Nếu nums[mid] == 0: Hoán đổi với low, tăng low++ và mid++.
- Nếu nums[mid] == 1: Tăng mid++.
- Nếu nums[mid] == 2: Hoán đổi với high, giảm high--.
Dữ liệu đầu vào (Input):
[2, 0, 2, 1, 1, 0]
Kết quả kỳ vọng (Expected Output):
[0, 0, 1, 1, 2, 2]
Dữ liệu đầu vào (Input):
[2, 0, 1]
Kết quả kỳ vọng (Expected Output):
[0, 1, 2]
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
