โปรแกรม Java หาตัวเลขที่เกิดขึ้นครั้งคี่ (Odd Occurrences)

โจทย์: หาตัวเลขที่เกิดขึ้นจำนวนครั้งคี่ ใน Array

สมมติมีเพียงตัวเดียวที่เกิดครั้งคี่ (อื่นๆ เป็นคู่)

วิธี 1: Bitwise XOR (Optimal - O(n) time, O(1) space)

คุณสมบัติ XOR: a ^ a = 0, a ^ 0 = a, a ^ b ^ a = b

คู่ที่เหมือนกันจะ cancel กันออก เหลือตัวที่ครั้งคี่

public class Demo {
    static int findOddOccurrence(int[] arr) {
        int result = 0;
        for (int num : arr) {
            result ^= num;
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] arr = {34, 56, 99, 34, 55, 99, 90, 11, 12, 11, 11, 34};
        // 34: 3 ครั้ง (คี่), 56: 1, 99: 2, 55: 1, 90: 1, 11: 3, 12: 1
        // XOR ทั้งหมด = 34 ^ 56 ^ 99 ^ 34 ^ 55 ^ 99 ^ 90 ^ 11 ^ 12 ^ 11 ^ 11 ^ 34
        // = (34^34^34) ^ (99^99) ^ (11^11^11) ^ 56 ^ 55 ^ 90 ^ 12
        // = 34 ^ 0 ^ 11 ^ 56 ^ 55 ^ 90 ^ 12
        // ต้องคำนวณต่อ...
        
        System.out.println("XOR Result: " + findOddOccurrence(arr));
    }
}

วิธี 2: HashMap Counting (O(n) time, O(n) space)

static int findOddOccurrenceMap(int[] arr) {
    Map count = new HashMap<>();
    for (int num : arr) {
        count.merge(num, 1, Integer::sum);
    }
    for (Map.Entry e : count.entrySet()) {
        if (e.getValue() % 2 != 0) {
            return e.getKey();
        }
    }
    return -1;
}

วิธี 3: Brute Force (O(n²) - โค้ดต้นฉบับ)

static int oddOccursBrute(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int count = 0;
        for (int j = 0; j < arr.length; j++) {
            if (arr[i] == arr[j]) count++;
        }
        if (count % 2 != 0) return arr[i];
    }
    return -1;
}

ผลลัพธ์ตัวอย่าง

XOR Result: 34

สรุป

ข้อสังเกต: โค้ดต้นฉบับใช้ Brute Force O(n²) ควรใช้ XOR หรือ HashMap แทน

โปรแกรม Java หาตัวอักษรแรกที่ไม่ซ้ำใน Stream ของ Characters

โปรแกรม Java หาคู่ที่ใกล้เคียงที่สุดจาก Sorted Arrays 2 อัน