Leetcode 169: Tìm số phiếu bầu chiếm đa số với thuật toán Boyer-Moore

Giải thích đề bài

Leetcode 169: Majority Element là bài toán được gắn tag dễ. Nhưng mình thấy bài này khá hay khi giới thiệu chúng ta thuật toán Boyer-Moore Majority Voting. Giải thích sơ lược qua về đề bài: giả sử đang diễn ra ngày bầu cử chủ tịch nước với bốn lá phiếu bầu A, B, C, D tương ứng cho 4 cử tri. Kết quả cuối cùng bạn nhận được là

A B B A A C A C C A A

Mục tiêu của bạn là tìm ra được số phiếu bầu chiếm đa số trong các phiếu bầu nhận được vào cuối ngày bầu cử để tìm ra được người chiến thắng cuộc bầu cử lần này. Điều kiện để trở thành chủ tịch nước là phải có số phiếu bầu lớn hơn phân nửa tổng số phiếu nhân được hay k > n / 2 với k là số phiếu bầu và n là tổng số phiếu bầu.

Một số cách giải không dùng Boyer-Moore Majority Voting

Sử dụng Hash Table để tìm sự lặp lại của các phiếu bầu

Có rất nhiều cách để giải bài này. Bạn có thể dùng Hash Table để tìm frequency của từng lá phiếu bầu và trả về cử tri với nhiều số phiếu nhất. Nếu áp dụng theo cách này với dữ liệu đầu vào trên thì ta sẽ có frequency_map tương ứng là

{
    "A" : 6,
    "B" : 2,
    "C" : 3
}

Vì số phiếu bầu A là 6 lớn hơn n/2 với n là 11 nên A là kết quả ta cần tìm. Tuy nhiên, với cách giải này, sẽ có space complexity là O(n) vì sẽ tốn thêm bộ nhớ để khởi tạo Hash Table. Và vì không thể xác định được có bao nhiêu phiếu bầu tổng cộng từ dữ liệu của đề bài, Hash Table phải liên tục khởi tạo lại để chứa thêm data. Để tìm hiểu thêm về cách  trong Hash Table, bạn có thể đọc dưới đây (vì Python dictionary được xây dựng từ Hash Table nên về căn bản thì cách hoạt động vẫn khá giống nhau)

Under the hood : Python Dictionary

Dictionary has always been a developer’s go to tool because of the unique relation between the key an...

DEV Communitysuvhotta

Sử dụng hàm sắp xếp

Một hướng giải quyết khác là sắp xếp mảng được chọn và kết quả cuối cùng trả về là phần tử vị trí thứ n/2 của mảng sau khi sắp xếp.

Input array: [A B B A A C A C C A A] 
Sorted array: [A A A A A A B B C C C]

Với mảng được sắp xếp trên, vị trí n/2 lúc này là 11/2 = 5 (làm tròn 5.5) là A tại index thứ 5 của mảng.

Thuật toán tìm số phiếu bầu chiếm đa số Boyer-Moore

Thuật toán tìm số phiếu bầu chiếm đa số Boyer-Moore (Boyer-Moore majority vote algorithm hay A Linear Time Majority Vote algorithm) là một thuật toán để tìm phần lớn chuỗi các phần tử sử dụng thời gian tuyến tính (linear time hay O(n)) và không gian không đổi (constant space hay O(1)). Nó được đặt theo tên của Robert S. Boyer và J Strother Moore, người đã xuất bản nó vào năm 1981.

Chi tiết hơn về thuật toán, để tìm ra được số phiếu bầu chiếm đa số, ta sẽ có 2 biến là majority để đánh dấu cho phiếu bầu chiếm đa số hiện tại và count là số phiếu bầu đếm được. Giá trị mặc định của 2 biến số trên sẽ là 0 (tương ứng với chưa gán). Sau đó, ta sẽ chạy vòng lặp từ đầu cho đến cuối mảng phiếu bầu. Sẽ có các điều kiện chính sau

• Nếu majority hoặc count bằng 0, gán phần tử hiện tại là majority và tăng biến đếm count lên 1 đơn vị
• Nếu phần tử khác với majority, giảm biến đếm 1 đơn vị
• Nếu phần tử bằng với majority, tăng biến đếm lên 1 đơn vị

Kết quả cuối cùng là majority sau khi kết thúc vòng lặp. Lưu ý, thuật toán này chỉ áp dụng được với mảng có chứa một phần tử chiếm đa số mảng hay bắt buộc phải có k > n/2 thì thuật toán mới hoạt động. Nếu không thoả điều kiện cần, majority cuối cùng sẽ là một phần tử bất kì chứ không chính xác.

Vì chỉ chạy 1 vòng lặp nên time complexity lúc này là O(n) và space complexity là O(1). Thoả yêu cầu đề bài 🎉. Bạn có thể xem code mẫu ở bên dưới.

Ứng dụng giải Leetcode 169

Vì ở đây mình nhúng Github Gist vào nên bạn chỉ có thể xem nếu dùng trình duyệt được hỗ trợ mã nhúng thôi nhé 🥲 Cảm ơn các bạn đã đọc đến cuối bài viết này.