Tìm phần tử duy nhất bị lặp lại trong khoảng 1 đến n – 1

Cho một mảng có size bằng n. Chứa các số được ramdom từ 1 đến n – 1, và mảng chỉ có duy nhất một phần x tử bị trùng lặp, tìm x.

Ví dụ:

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

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

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

B1: Khởi tạo i = 0;
B2: Loop i từ 0 đến N - 2
    + Khởi tạo j = i + 1
    + Loop j từ i + 1 đến N - 1
      -> Nếu arr[i] == arr[j] return arr[i]

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 1, 4, 5, 6};
        System.out.println("Element repetitive is: " + findRepeat(arr, arr.length));
    }

    public static int findRepeat(int[] arr, int n) {
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] == arr[j])
                    return arr[i];
            }
        }
        return -1;
    }
}

Output: Element repetitive is: 1
Độ phức tạp: θ(n²)

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

Ta có 1 + 2 + 3 + … + n – 1 = n(n – 1)/2.
Tổng các phần tử của mảng là: 1 + 2 + 3 + n – 1 + x, với x là một số bị lặp lại có giá trị trong khoảng [1, n]. 
=> Sum(arr_0->n-1)) – Sum(n * (n – 1)/2)) = x

public class Main {
   public static void main(String[] args) {
        int[] arr = {1, 2, 3, 1, 4, 5, 6};
       System.out.println("Element repetitive is: " + findRepeat(arr, arr.length));
    }

    public static int findRepeat(int[] arr, int n) {
        int sum = 0;
        for(int value : arr) {
            sum += value;
        }
        int formula = n * (n - 1) / 2;
        return sum - formula;
    }
}

Output: Element repetitive is: 1
Độ phức tạp: θ(n) chi phí duyệt mảng để tính tổng tất cả các phần tử.

Cách 3: Sử dụng HasSet

B1: Khởi tạo HashSet s
B2: Loop mỗi phần tử i trong mảng
    + Nếu s chứa arr[i] return arr[i]
    + Ngược lại thêm arr[i] vào s

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Main {
   public static void main(String[] args) {
        int[] arr = {1, 2, 3, 1, 4, 5, 6};
        System.out.println("Element repetitive is: " + findRepeat(arr, arr.length));
    }
    public static int findRepeat(int[] arr, int n) {
        Set set = new HashSet();
        for(int value : arr) {
            if (set.contains(value))
                return value;
            else set.add(value);
        }
        return -1;
    }
}

Output: Element repetitive is: 1
Độ phức tạp: θ(n) chi phí duyệt mảng. 

Link full source-code: source

Nguồn tham khảo: geeksforgeeks