Phần tử đa số (Majority Element) trong Java – Tìm phần tử xuất hiện > n/2 lần

Cho một mảng số nguyên. Phần tử đa số là phần tử xuất hiện nhiều hơn n/2 lần (n là kích thước mảng). Bài toán yêu cầu tìm phần tử này (nếu có).

Ví dụ

Đầu vào: {1, 2, 4, 3, 3, 1, 1, 5} (n=8) → Không có phần tử nào > 4 lần.

Đầu vào: {2, 1, 1, 2, 2, 2} (n=6) → Phần tử 2 xuất hiện 4 lần > 3 → Kết quả: 2.

Cách 1: HashMap (Đếm tần suất) – O(n) time, O(n) space

import java.util.*;

public class MajorityElement {
    public static int findMajority(int[] arr) {
        Map freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry e : freq.entrySet()) {
            if (e.getValue() > arr.length / 2) return e.getKey();
        }
        return -1; // không có phần tử đa số
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 1, 2, 2, 2};
        int ans = findMajority(arr);
        System.out.println(ans != -1 ? "Phần tử đa số: " + ans : "Không có phần tử đa số");
    }
}

Cách 2: Thuật toán Boyer-Moore Voting – O(n) time, O(1) space (Tối ưu)

Ý tưởng: Duyệt mảng, giữ một ứng cử viên và đếm. Nếu đếm = 0, chọn phần tử hiện tại làm ứng cử viên mới. Cuối cùng kiểm tra ứng cử viên có thực sự là đa số không.

public class MajorityElementOptimized {
    public static int findMajority(int[] arr) {
        int candidate = 0, count = 0;
        // Phase 1: Tìm ứng cử viên
        for (int num : arr) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        // Phase 2: Xác minh
        count = 0;
        for (int num : arr) if (num == candidate) count++;
        return (count > arr.length / 2) ? candidate : -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 1, 2, 2, 2};
        System.out.println("Kết quả: " + findMajority(arr)); // 2
    }
}

So sánh

Lưu ý: Nếu bài toán chỉ yêu cầu phần tử xuất hiện nhiều nhất (không nhất thiết > n/2), hãy dùng HashMap hoặc sort rồi đếm.