Sau sắp xếp, từng ô phải khớp
Với dãy `a` gồm `n ≥ 1` số, bài toán hỏi `a` có chứa đúng mỗi số từ 1 đến `n` một lần hay không. Ý tưởng đầu là sắp `a` tăng dần, rồi so với `[1, 2, …, n]`. Làm mịn thành hai việc cụ thể: tạo bản sao đã sắp và kiểm `b[i] == i+1` ở từng chỉ số `i`. Nếu một ô không khớp, trả `False` ngay; nếu tất cả đều khớp, trả `True`. Chẳng hạn `[3, 1, 2]` được sắp thành `[1, 2, 3]` nên đạt, còn `[3, 1, 1]` thành `[1, 1, 3]` nên không đạt.
Mã hoàn chỉnh và dữ liệu thử
Mã dùng `sorted(a)` để tạo bản đã sắp; ý tưởng sắp xếp và so từng ô giống các bước trong SGK, nhưng dãy gốc không bị đổi:
```python
def la_hoan_vi_sap_xep(a):
n = len(a)
if n == 0:
return False
b = sorted(a)
for i in range(n):
if b[i] != i + 1:
return False
return True
print(la_hoan_vi_sap_xep([3, 1, 2]))
print(la_hoan_vi_sap_xep([3, 1, 1]))
```
Hai kết quả là `True` và `False`. Trong bài này quy ước `n ≥ 1`; dãy rỗng được trả `False` vì không nằm trong yêu cầu. Nếu muốn tự cài đặt sắp xếp, có thể dùng thuật toán chèn đã học thay cho `sorted` mà vẫn giữ bước so sánh.
Bài luyện
Dãy nào là hoán vị của `[1, 2, 3, 4]`?
Thiếu 3 và lặp 2.
Đủ bốn số 1,2,3,4, mỗi số một lần.
Có 0 thay vì 1.
Chỉ có ba phần tử.
Lời giải
Sắp [4,2,1,3] được [1,2,3,4], đúng dãy cần đối chiếu.
Bài luyện
Sau khi sắp tăng một dãy `a` dài `n`, cần so `b[i]` với giá trị nào?
Python đánh chỉ số từ 0 còn dãy chuẩn bắt đầu ở 1.
Ở chỉ số 0 cần số 1; ở chỉ số i cần số i+1.
Giá trị này vượt dãy chuẩn.
So với ô trước không bảo đảm đủ 1..n.
Lời giải
Dãy chuẩn là [1,2,...,n], nên phần tử ở chỉ số i bằng i+1.
Bài luyện
Vì sao mã trong bài dùng `sorted(a)` thay vì sắp trực tiếp `a`?
sorted tạo danh sách mới.
Vẫn phải đối chiếu từng ô.
Sắp thứ tự không sửa giá trị thiếu/lặp.
sorted không loại phần tử trùng.
Lời giải
Hàm chỉ trả kết quả kiểm tra; sorted(a) tạo b đã sắp mà không đổi a.
Đang học