Một nhóm liên tiếp, một số đếm
Nếu dãy `a` đã được sắp **không giảm**, các giá trị bằng nhau nằm thành từng đoạn liên tiếp. Với `[1, 1, 2, 4, 4, 4]`, ba đoạn có độ dài 2, 1, 3; điền độ dài của mỗi đoạn vào các vị trí của đoạn cho `[2, 2, 1, 3, 3, 3]`. Có thể giữ hai chỉ số: `start` là đầu đoạn; `end` là vị trí đầu tiên khác giá trị ấy. Độ dài đoạn là `end-start`. Không dùng cách này cho dãy chưa sắp, vì cùng một giá trị có thể nằm ở các đoạn tách nhau.
Duyệt các đoạn mà không đếm lại từ đầu
```python
def dem_day_da_sap(a):
b = [0] * len(a)
start = 0
while start < len(a):
end = start + 1
while end < len(a) and a[end] == a[start]:
end += 1
for i in range(start, end):
b[i] = end - start
start = end
return b
print(dem_day_da_sap([1, 1, 2, 4, 4, 4]))
```
Kết quả là `[2, 2, 1, 3, 3, 3]`. Mỗi phần tử được duyệt trong đoạn của nó và được ghi vào `b` một lần, nên số bước tăng theo `n`: `O(n)` với đầu vào đã sắp. Với dãy rỗng, kết quả là dãy rỗng.
Bài luyện
Với dãy đã sắp `[2, 2, 2, 5, 5]`, kết quả đếm theo vị trí là gì?
Đây là số thứ tự trong từng nhóm.
2 có ba lần, 5 có hai lần.
Đây là dãy gốc.
Không giá trị nào xuất hiện năm lần.
Lời giải
Ba số 2 liên tiếp nhận số đếm 3; hai số 5 liên tiếp nhận số đếm 2.
Bài luyện
Vì sao cách duyệt theo đoạn liên tiếp cần điều kiện dãy đã sắp?
Khi ấy một đoạn bằng nhau chứa đủ các lần lặp của giá trị đó.
Dãy đã sắp vẫn có thể có số trùng.
Số âm cũng sắp được.
Vẫn cần ghi b theo từng vị trí.
Lời giải
Nếu a chưa sắp, một giá trị có thể xuất hiện ở nhiều đoạn rời nhau, nên độ dài một đoạn không là tổng số lần xuất hiện.
Bài luyện
Với đầu vào đã sắp, mã `dem_day_da_sap` có bậc thời gian nào theo n?
Mã vẫn xem các phần tử.
Không chia đôi phạm vi.
Mỗi đoạn được duyệt và ghi một lượt, tổng tỉ lệ n.
Không đếm lại cả dãy cho mỗi phần tử.
Lời giải
Mỗi phần tử thuộc đúng một đoạn; tổng lượt tìm ranh giới và ghi b tăng tuyến tính theo n.
Đang học