Mô phỏng thuật toán Bầu chọn đa số (Boyer-Moore)

Boyer-Moore Majority Vote · Nhóm: Mảng

Tìm phần tử xuất hiện quá nửa mảng chỉ với một lượt duyệt và O(1) bộ nhớ (Boyer-Moore).

Ý tưởng

Giữ một ứng viên và một bộ đếm, ban đầu đếm bằng 0.

Khi đếm về 0, nhận phần tử hiện tại làm ứng viên mới.

Gặp phần tử trùng ứng viên thì đếm +1, khác thì đếm -1 · ứng viên còn sống cuối cùng là đa số.

Vì sao đúng

Mỗi phần tử khác ứng viên triệt tiêu đúng một phiếu · nếu một giá trị chiếm quá nửa thì không thể bị triệt tiêu hết, nên nó sống sót mà chỉ cần hai biến.

Mã Python

def majority(a):
    candidate = None
    count = 0
    for x in a:                    # single left-to-right pass
        if count == 0:
            candidate = x          # adopt a fresh candidate
        if x == candidate:
            count += 1             # a vote for the candidate
        else:
            count -= 1             # cancels one candidate vote
    return candidate               # survives if it appears > n/2 times

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.