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

B1: Khởi tạo HashMap<Key, count> map với Key là giá trị của các phần tử trong mảng B2: Loop qua các phần tử của mảng, Với mỗi phần tử arr[i]       + If map.contains(arr[i]] thì update count = count + 1       + Else: map.put(arr[i], 1)  B3: Loop map, nếu count = 1 thì return key

Cách 3: Sắp xếp

B1: Sắp xếp mảng B2: Loop mảng, với mỗi phần tử arr[i]        + Khởi tạo count = 0        + If (arr[i] == arr[i + 1] thì count++        + Else If ( count == 0) return arr[i]        + Else count = 0

Cách 4: Xor

Nhắc lại phép xor

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

 

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

Ví dụ Input: arr[] = {4, 3, 6, 4, 6, 7, 3} res = 4 ^ 3 ^ 6 ^ 4 ^ 6 ^ 7 ^ 3 res = 4 ^ 4 ^ 3 ^ 3 ^ 6 ^ 6 ^ 7 res = 0 ^ 0 ^ 0 ^ 7 res = 7

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;
    }
    
}

Output: Value single is: 5 Độ phức tạp:  θ(n)

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

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

2 * (a + b + c + d) – {a + b + c + d + b + c + a} = d 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

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;
    }
}

Output: Value single is: 5 Độ phức tạp:  θ(n)

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