Tìm phần tử chỉ xuất hiện một lần trong mảng

Viết chương trình tìm phần tử chỉ xuất hiện một lần trong mảng, các phần tử còn lại của mảng luôn xuất hiện 2 lần.

Ví dụ

Input: arr[] = {1, 2, 1, 2, 3, 4, 5, 5, 4}
Output: 3

Cách 1: Sử dụng 2 vòng lặp

Sử dụng 2 vòng lặp for để đếm số lần xuất hiện của một phần tử trong mảng. 
Độ phức tạp: θ(n²)

Cách 2: Sử dụng Hash

Cách 3: Sắp xếp

Cách 4: Xor

Nhắc lại phép xor

Cách đơn giản để nhớ phép xor là giống nhau là 0, khác nhau là 1. Dựa vào đây, chúng ta chỉ xor tất cả các phần tử của mảng thì sẽ tìm ra phần tử duy nhất trong mảng

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 7, 1, 3, 4, 9, 5, 6, 6, 7, 2, 8, 8, 4, 9};
        System.out.println("Value single is: " + findElementSingle_Xor(arr, arr.length));
    }
    
    public static int findElementSingle_Xor(int[] arr, int n) {
        int res = arr[0];
        for(int i = 1; i < n; i++) {
            res = res ^ arr[i];
        }
        return res;
    }
    
}

Cách 5: Công thức tổng quát

Ta có mảng arr = {a, b, c, d, b, c, a}

B1: Khởi tạo HashSet s
B2: Loop mảng, với mỗi phần tử arr[i] thì s.add(arr[i])
B3: Khởi tạo dupSumSignle = 0
    + Loop s, với mỗi phần tử s[i] dupSumSignle += s[i]
B4: Khởi tạo sum = 0
    + Loop arr với mỗi phần tử arr[i] sum += arr[i]
B5: return dupSumSignle - sum

import java.util.*;
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 7, 1, 3, 4, 9, 5, 6, 6, 7, 2, 8, 8, 4, 9};
        System.out.println("Value single is: " + findElementSingle_Formula(arr, arr.length));
    }
    

    // 2 * (a + b + c + d) - (a + a + b + b + c + c + d) = d
    public static int findElementSingle_Formula (int[] arr, int n) {
        Set set = new HashSet();
        for(int value : arr)
            set.add(value);
        int dupSumSignle = 0;
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()){
            dupSumSignle += iterator.next();
        }

        dupSumSignle *= 2;

        int sumArr = 0;
        for(int value : arr)
            sumArr += value;
        return dupSumSignle - sumArr;
    }
}

Full soure của 5 cách trên: SourceCode