Đây là bài toán tìm các phần tử bị trùng lặp trong một mảng cho trước. Có nhiều cách để giải quyết vấn đề này, tuy nhiên mỗi phương pháp sẽ có độ phức tạp thời gian (Time Complexity) và độ phức tạp không gian (Space Complexity - bộ nhớ) khác nhau. Do đó, bài toán thường đi kèm với các điều kiện ràng buộc bổ sung, ví dụ như: "Hãy giải bài toán với độ phức tạp không gian là $O(1)$".

Cách 1: Sử dụng vòng lặp lồng nhauPhương pháp đầu tiên là chọn từng phần tử trong mảng và so sánh nó với tất cả các phần tử còn lại.

Cách này có độ phức tạp thời gian là $O(n^2)$, nhưng vì không sử dụng thêm bộ nhớ ngoài nên độ phức tạp không gian là $O(1)$.
public void printDuplicateNumbers(int[] numbers) {
    for(int i = 0; i < numbers.length; i++) {
        for(int j = i + 1; j < numbers.length; j++) {
            if (numbers[i] == numbers[j]) {
                System.out.println("Số trùng lặp: " + numbers[i]);
            }
        }
    }
}

Cách 2: Sử dụng Sắp xếp (Sorting)Phương pháp thứ hai là sắp xếp mảng trước, sau đó lặp qua các phần tử để so sánh cặp phần tử đứng cạnh nhau. Độ phức tạp thời gian phụ thuộc vào thuật toán sắp xếp, thường là $O(n log n)$, và độ phức tạp không gian là $O(n)$ (hoặc tùy thuộc vào cách triển khai hàm sort).

public static void printDuplicateNumbersBySort(int[] numbers) {
    Arrays.sort(numbers);
    for(int i = 0; i < numbers.length - 1; i++) {
        if (numbers[i] == numbers[i + 1]) {
            System.out.println("Số trùng lặp: " + numbers[i]);
        }
    }
}

Cách 3: Sử dụng Set (Tập hợp)Phương pháp cuối cùng là sử dụng đối tượng Set – một cấu trúc dữ liệu không cho phép lưu trữ các giá trị trùng lặp. Với cách này, chúng ta chỉ cần kiểm tra từng phần tử trong mảng một lần duy nhất, nên độ phức tạp thời gian là $O(n)$. Tuy nhiên, vì phải lưu trữ các phần tử vào Set, độ phức tạp không gian sẽ là $O(n)$.

public static void printDuplicateNumbersBySet(int[] numbers) {
    java.util.Set<Integer> numberSet = new HashSet<>();
    for (int i : numbers) {
        Integer number = i; // Tự động đóng gói (autoboxing)
        if (numberSet.contains(number)) {
            System.out.println("Số trùng lặp: " + number.intValue());
        } else {
            numberSet.add(number);
        }
    }
}
Nguồn bài viết ryukato.github.io