Tìm phần tử trùng lặp trong mảng hằng với phần tử 0 đến N-1 trong O(1) không gian trong C++

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. Ví dụ n=7, [5,2,3,5,1,6,2,3,4,5] → 5,2,3.

Với mỗi phần tử e, lấy giá trị tuyệt đối. Nếu A[|e|] dương thì đổi âm, nếu đã âm thì đó là phần tử lặp.

Ví dụ

#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ả

5 2 3 1