# 229. Majority Element II
## I/ Tóm tắt đề bài
- Cho dãy gồm $n$ phần tử, tìm các giá trị xuất hiện nhiều hơn $\lfloor \frac{n}{3} \rfloor$.

## II/ Lời giải
- Với mỗi phần tử, ta sẽ đếm số lần xuất hiện của nó trong dãy đã cho, do giá trị của các phần tử khá lớn nên:
+ Cần sử dụng các cấu trúc dữ liệu (`map`, `unordered_map`, `gp_hash_table` trong C++ hoặc dictionary trong Python).
+ Hoặc dùng rời rạc hóa để đếm bằng mảng. Phương pháp tuy có độ phức tạp lý thuyết là $O(n \log n)$ nhưng trong trường hợp bộ dữ liệu lớn vẫn nhanh hơn sử dụng trực tiếp cấu trúc dữ liệu do hằng số nhỏ; nó cũng sử dụng ít bộ nhớ hơn.
- Sau khi đếm xong, ta sẽ kiểm tra từng giá trị xem có xuất hiện nhiều hơn $\lfloor \frac{n}{3} \rfloor$ không, nếu có thì giá trị này là đáp án.

## III/ Nhận xét
- Bài toán có độ phức tạp trung bình $O(n)$ nếu sử dụng Hash map hay $O(n \log n)$ nếu sử dụng cấu trúc dữ liệu dạng cây hay rời rạc hóa.

## IV/ Follow up
- Đề bài yêu cầu sử dụng thuật toán có độ phức tạp thời gian $O(n)$ và độ phức tạp không gian $O(1)$. Một thuật toán rất nổi tiếng để tìm phần tử đa số là thuật toán Boyer-Moore để tìm phiếu bầu đa số.
- Tuy nhiên người viết không biết thuật toán này 😭, nên đã thử làm cách khác bậy hơn nhưng cũng không kém phần thú vị.
- Thuật toán ngẫu nhiên:
+ Đầu tiên ta có nhận xét nếu một phần tử xuất hiện nhiều hơn$\lfloor \frac{n}{3} \rfloor$, nếu ta chọn ngẫu nhiên một phần tử trong dãy, tỉ lệ ta có được phần tử đa số đó là ít nhất $\frac{1}{3}$.
+ Ta tiến hành chọn ra $s$ phần tử ngẫu nhiên trong dãy, những giá trị nào có tỉ lệ xuất hiện quá $p$ trong $s$ lần chọn này, nó sẽ là một ứng viên cho phần tử đa số. Với $s$ và $p$ là các hằng số ta chọn.
+ Để chắc chắn một phần tử là phần tử đa số, ta sẽ đếm lại số lần xuất hiện của nó trong dãy. Do số lần xuất hiện của nó phải lớn hơn $p$ nên ta chỉ phải kiểm tra nhiều nhất $\frac{1}{p}$ lần.
- Chứng minh độ chính xác của thuật toán
+ Giả sử ta có phần tử $x$ chỉ xuất hiện vừa đúng hơn $\lfloor \frac{n}{3} \rfloor$, tỉ lệ chọn ra phần tử $x$ là khoảng $\frac{1}{3}$.
+ Tỉ lệ để chọn ra chính xác $i$ lần $x$ trong $s$ lần chọn là $P(i) = \binom{s}{i} \times (\frac{1}{3})^i \times (\frac{2}{3})^{s-i}$. Với $\binom{s}{i}$ số cách chọn ra $i$ những phần từ đúng là $x$, $(\frac{1}{3})^i$ là tỉ lệ chọn ra đúng $i$ phần tử là $x$ và $(\frac{2}{3})^{s-i}$ là tỉ lệ chọn những phần tử còn lại không phải $x$.
+ Vì thế ta không kiểm tra đúng phần tử đa số, nghĩa là tỉ lệ nó xuất hiện không quá $p$ là $\sum_{i=0}^{S \times p} P(i)$. Ví dụ nếu chọn $s$ là $100$ và $p$ là $0.15$ thì tỉ lệ này khoảng $0.002\%$, có thể giảm $p$ để tăng thêm tỉ lệ chính xác nữa.
+ Trên lí thuyết, đúng như theo yêu cầu đề bài, thuật toán có độ phức tạp thời gian $O(n)$ và độ phức tạp không gian $O(1)$. Tuy vậy thuật toán hơi "gian lận" vì đây không phải thuật toán tất định và hằng số cũng lớn hơn.

## V/ Tham khảo
- [Thuật toán Booye-Moore](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm)
- [Rời rạc hóa và ứng dụng](https://vnoi.info/wiki/algo/trick/Roi-rac-hoa-va-ung-dung.md)