Câu hỏi
Cho một mảng A các số nguyên a[i], tìm cách sắp xếp mảng sao cho phần tử thứ nhất nhỏ hơn phần tử thứ hai, phần tử thứ hai lớn hơn phần tử thứ ba, phần tử thứ ba nhỏ hơn phần tử thứ tư v.v... Tức là:
a[0] <= a[1] >= a[2] <= a[3] >= a[4] ...
Ta gọi một mảng có thứ tự như vậy là một mảng đã được sắp xếp lắc lư (wiggly sorted).
Phân tích
Ta nhận xét rằng yêu cầu thứ tự chỉ áp dụng vào hai phần tử lân cận của phần tử đang xét. Ví dụ, phần tử a[1] chỉ cần lớn hơn hai phần tử a[0] và a[2], ngoài ra không còn quan hệ với phần tử nào nữa. Điều đó dẫn đến ý tưởng giải sẽ rất có thể ở dạng tham ăn (greedy algorithm).
Giả sử như ta đã có mảng A' có độ dài 2n (chẵn) thỏa mãn điều kiện. Phần tử kế tiếp (2n + 1) vì ở vị trí lẻ nên sẽ phải nhỏ hơn phần tử cuối cùng trong mảng, đồng thời cũng phải đảm bảo nhỏ hơn phần tử sau đó (2n + 2). Vì ta không biết phần tử (2n + 2) sẽ có giá trị bao nhiêu nên cách an toàn nhất để thỏa mãn hai điều kiện cho phần tử 2n + 1 là chọn phần tử nhỏ nhất trong số các phần tử còn lại của A.
Lập luận tương tự cho thấy rằng phần tử ở vị trí chẵn nên có giá trị lớn nhất trong số các phần tử còn lại.
Tóm lại, cách giải câu hỏi này sẽ bao gồm hai bước chính:
- Sắp xếp mảng A theo thứ tự tăng dần.
- Lần lượt gán a[0] = min(A), và a[1] = max(A[1 : ]), và a[2] = min(A[2 : ]), v.v...
Dĩ nhiên là ta không cần gọi min hay max mà chỉ cần giữ hai biến chỉ mục từ đầu, và cuối mảng A để tìm ngay giá trị cực tiểu hay cực đại vì A đã được sắp xếp ở bước đầu tiên.
Độ phức tạp thực thi của cách giải này phụ thuộc vào thuộc toán sắp xếp sử dụng ở bước đầu tiên.
Vấn đề cài đặt cách giải xin được để lại cho bạn đọc. Diễn đàn là nơi tốt nhất để trao đổi về các yếu tố liên quan đến cài đặt.
Tổng kết
Qua loạt bài Phỏng vấn, tác giả hy vọng rằng bạn đọc nhận ra được sự quan trọng của bộ kiến thức nền tảng, đặc biệt là các cấu trúc dữ liệu phổ biến. Từ các kiến thức nền tảng này, chúng ta có thể giải quyết được rất nhiều những vấn đề khác.
Python cùng với phương châm kèm cả pin đem đến cho chúng ta một loạt các cấu trúc dữ liệu qua các kiểu, hoặc mô-đun có sẵn. Python thật sự là một công cụ mạnh mẽ và hữu ích.