Chương trình C++ tìm phần tử trùng lặp O(n) thời gian O(1) không gian - Phần 1

Cho danh sách số từ 0 đến n-1. Số có thể lặp nhiều lần. Tìm các số lặp không dùng không gian thêm. n=7, danh sách [5,2,3,5,1,6,2,3,4,5] → 5, 2, 3.

Giải pháp: với mỗi phần tử e, lấy chỉ số = |e|. Nếu A[chỉ số] > 0 thì đổi âm, ngược lại là phần tử lặp.

Ví dụ mã nguồn

#include <iostream>
#include <cmath>
using namespace std;

void findDuplicates(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        if (arr[abs(arr[i])] >= 0)
            arr[abs(arr[i])] *= -1;
        else
            cout << abs(arr[i]) << " ";
    }
}

int main() {
    int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    findDuplicates(arr, n);
}

Kết quả đầu ra

5 2 3 1