Tìm phần tử đầu tiên bị lặp lại trong mảng

Cho một mảng số nguyên n phần tử. Tìm phần từ bị lặp lại trong mảng. Nếu có nhiều phần tử bị lặp lại thì in một phần tử bất kỳ, nếu không có phần tử nào bị lặp lại in ra “NO”.

Ví dụ:

Input: arr[] = {1, 4, 5, 7, 4, 9, 5}
Output: 4

Cách đơn giản để làm bài này là chúng ta có thể sử dụng 2 vòng lặp lồng nhau để kiểm tra từng phần tử có xuất hiện lại ở phía sau mảng hay không. Cách này sẽ tiêu tốn O(n²) và thường không sử dụng cho các tập dữ liệu lớn.

Để xem nào! um chúng ta cũng có thể sắp xếp mảng tăng dần rồi duyệt từng phần xem phần tử kế tiếp của nó có giống nhau hay không nếu có tất là phần tử bị trùng rồi

Code một xíu nhé

public static void findElementRepearSorted(int[] arr, int n) {
    Arrays.sort(arr);
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] == arr[i+ 1]){
            System.out.println(arr[i]);
            return;
        }
    }
    System.out.println("NO");
}

Output: 4

Độ phức tạp O(nlog(n).

Um, Mình vẫn chưa hài lòng với tốc độ này lắm, thử nghĩ xem còn cách nào khác không.

Chúng ta nhớ lại chi phí tìm kiếm của HashSet là O(1), vậy tại sao chúng ta không dùng HashSet để lưu từng phần tử đã duyệt qua, và cứ mỗi phần tử mới ta lại tìm kiếm xem trong HashSet có chứa hay không, nếu có tất là đã bị lặp lại rồi.

public static void findElementRepeatHash(int[] arr, int n) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if(set.contains(arr[i])){
                System.out.println(arr[i]);
                return;
            } else {
                set.add(arr[i]);
            }
        }
        System.out.println("NO");
    }

Output: 4

Độ phức tạp: O(n).

Full source code cho cả 3 cách: source