การหา Majority Element ใน Java (องค์ประกอบที่ปรากฏมากกว่าครึ่งหนึ่ง)

Majority Element คือองค์ประกอบที่ปรากฏในอาร์เรย์มากกว่า n/2 ครั้ง (โดย n คือขนาดอาร์เรย์) กล่าวคือ ต้องปรากฏอย่างน้อย floor(n/2) + 1 ครั้ง

ตัวอย่าง Input-1

N = 8
A[] = {1, 2, 4, 3, 3, 1, 1, 5}

Output

1

คำอธิบาย: ตัวเลข 1 ปรากฏ 3 ครั้ง (ไม่เกิน 8/2 = 4) → จริงๆ แล้วตัวอย่างนี้ไม่มี majority element (อาจเป็นข้อผิดพลาดในตัวอย่างต้นฉบับ)

ตัวอย่าง Input-2

N = 6
A[] = {1, 5, 4, 4, 1, 1}

Output

1

คำอธิบาย: ตัวเลข 1 ปรากฏ 3 ครั้ง = 6/2 → ไม่เกินครึ่ง (ต้อง > 3) → ก็ไม่ใช่ majority element

ตัวอย่างที่ถูกต้อง

N = 6
A[] = {2, 1, 1, 2, 2, 2}

Output

2

คำอธิบาย: ตัวเลข 2 ปรากฏ 4 ครั้ง > 6/2 = 3 → เป็น Majority Element

แนวทางแก้ปัญหา

วิธีที่ 1: ใช้ HashMap (Time: O(n), Space: O(n))

นับความถี่ของแต่ละตัวเลข แล้วตรวจสอบว่ามีตัวไหนเกิน n/2 หรือไม่

วิธีที่ 2: Boyer-Moore Voting Algorithm (Time: O(n), Space: O(1)) - แนะนำ

อัลกอริทึมนี้ใช้หลักการ "จับคู่ตัดกัน" ระหว่าง majority element กับ non-majority element

1. ตั้งค่า candidate = null, count = 0
2. วนลูปผ่านอาร์เรย์:
   • ถ้า count == 0: ตั้ง candidate = arr[i], count = 1
   • ถ้า arr[i] == candidate: count++
   • อื่นๆ: count--
3. หลังจบลูป candidate จะเป็นตัวที่น่าจะเป็น majority (ต้อง verify อีกครั้ง)

ตัวอย่างโค้ด (HashMap Approach)

import java.util.*;

public class MajorityElement {
    public static int findMajorityElement(int[] arr, int n) {
        Map freqMap = new HashMap<>();

        // นับความถี่
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // ตรวจสอบ majority
        for (Map.Entry entry : freqMap.entrySet()) {
            if (entry.getValue() > n / 2) {
                return entry.getKey();
            }
        }
        return -1; // ไม่มี majority element
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 1, 2, 2, 2};
        int n = arr.length;
        int result = findMajorityElement(arr, n);

        if (result != -1) {
            System.out.println("Majority Element is: " + result);
        } else {
            System.out.println("No majority element in array");
        }
    }
}

ตัวอย่างโค้ด (Boyer-Moore Voting Algorithm - แนะนำ)

public class MajorityElement {
    public static int findMajorityElement(int[] arr) {
        int candidate = 0;
        int count = 0;

        // Phase 1: หา candidate
        for (int num : arr) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        // Phase 2: Verify candidate
        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};
        int result = findMajorityElement(arr);
        System.out.println(result != -1 ? "Majority Element: " + result : "No majority element");
    }
}

ผลลัพธ์

Majority Element is: 2

สรุป