Cấu trúc dữ liệu & Giải thuật

Thực hành đếm tần suất và tìm phần tử xuất hiện nhiều nhất

Dùng bảng băm và quy tắc phá hòa rõ ràng cho mã học phần.

Thực hànhThực hành4 phút đọcPython

Hai từ cùng tần suất 2: ASP đứng trước TEST theo thứ tự chữ cái. Mở hình lớn ↗

1. Đề bài

Cho dãy ASP, TEST, ASP, ANDROID, TEST. Đếm số lần xuất hiện từng mã và lấy mã có tần suất lớn nhất. Nếu bằng nhau, chọn mã đứng trước theo thứ tự chữ cái.

2. Dự đoán bảng kết quả

ASP và TEST đều xuất hiện hai lần, ANDROID xuất hiện một lần. Chọn ASP vì đứng trước TEST. Để xử lý đầu vào rỗng, quy ước không có mã thắng. Nêu quy tắc đó trước khi chạy kiểm thử.

3. Đối chiếu lời giải

Mã tăng bộ đếm của khóa hiện tại khi đọc mỗi phần tử. Chọn ứng viên với khóa sắp xếp gồm âm của số lần xuất hiện và mã. Trường hợp rỗng trả None. Đảo thứ tự đầu vào để xem quy tắc phá hòa vẫn cho cùng kết quả.

Chạy ví dụ bằng python hoc_gt_dem_tan_suat.py.

Môi trường thực hành. Python 3.10 trở lên. Ví dụ dùng thư viện chuẩn Python.

Python · hoc_gt_dem_tan_suat.pyTải mã nguồn

def thong_ke(day):
    dem = {}
    for ma in day:
        dem[ma] = dem.get(ma, 0) + 1
    chon = min(dem, key=lambda ma: (-dem[ma], ma), default=None)
    return dem, chon

day = ["ASP", "TEST", "ASP", "ANDROID", "TEST"]
assert thong_ke(day) == ({"ASP": 2, "TEST": 2, "ANDROID": 1}, "ASP")
assert thong_ke(reversed(day))[1] == "ASP"
assert thong_ke([]) == ({}, None)
print(thong_ke(day))

4. Bài tập mở rộng

Đổi yêu cầu sang chọn mã xuất hiện sớm nhất nếu bằng tần suất. Hãy lưu vị trí xuất hiện đầu tiên khi đọc mã mới rồi sửa tiêu chí so sánh. Kiểm tra với dãy ban đầu và dãy đảo.

Đọc thêm Tài liệu giải thuật của Princeton.