Độ dài n cùng các giá trị cần có
Một dãy `n ≥ 1` phần tử là hoán vị của 1 đến `n` khi mỗi giá trị 1, 2, …, `n` đều xuất hiện. Vì có đúng `n` chỗ và `n` giá trị khác nhau bắt buộc phải có, không còn chỗ cho một giá trị lặp hoặc ngoài khoảng. Ví dụ `[2, 3, 1]` có đủ 1, 2, 3; `[1, 1, 3]` thiếu 2. Đây là cách làm mịn theo từng giá trị cần kiểm, không cần sắp lại dữ liệu.
Dừng ngay khi gặp số bị thiếu
```python
def la_hoan_vi_du_gia_tri(a):
n = len(a)
if n == 0:
return False
for x in range(1, n + 1):
if x not in a:
return False
return True
print(la_hoan_vi_du_gia_tri([2, 3, 1]))
print(la_hoan_vi_du_gia_tri([1, 1, 3]))
```
Kết quả là `True` rồi `False`. Phép `x in a` phải tìm trong dãy ở mỗi lượt; với dãy dài `n`, cách này có thể xét tới khoảng `n²` phần tử trong trường hợp xấu. Với bài thực hành ngắn, cách viết dễ theo dõi; nếu dữ liệu lớn, có thể chọn cấu trúc kiểm tra nhanh hơn sau khi đã hiểu điều kiện đúng.
Bài luyện
Dãy `[1, 1, 3]` dài 3 không phải hoán vị vì thiếu giá trị nào?
1 xuất hiện hai lần.
Dãy chuẩn 1..3 cần có 2.
3 đã có.
4 không thuộc 1..3.
Lời giải
Ba giá trị cần có là 1, 2, 3; dãy đã có 1 và 3 nhưng thiếu 2.
Bài luyện
Vì sao kiểm từng số từ 1 đến n có trong dãy dài n là đủ để kết luận hoán vị?
Thứ tự ban đầu có thể bất kì.
Không còn vị trí để chứa số lặp hoặc số ngoài 1..n.
Số âm sẽ làm thiếu ít nhất một số cần có.
Phải kiểm đủ n giá trị.
Lời giải
Khi mỗi số trong 1..n đều có mặt, n giá trị khác nhau đã lấp đúng n phần tử của dãy.
Bài luyện
Với mã dùng `x in a` ở mỗi lượt, điều gì đúng khi n tăng?
in có thể duyệt nhiều phần tử.
Có n giá trị x cần kiểm, mỗi lần có thể duyệt n ô.
Không có bảo đảm như vậy.
Phép in tìm trong a.
Lời giải
Vòng ngoài có n lượt; phép kiểm x in a có thể phải xem tới n phần tử mỗi lượt, nên trường hợp xấu có bậc O(n²).
Đang học