Giả sử có danh sách số từ 0 đến n-1. Một số có thể lặp lại nhiều lần. Tìm các số lặp lại mà không dùng không gian thêm. Ví dụ n=7, danh sách [5, 2, 3, 5, 1, 6, 2, 3, 4, 5] → kết quả 5, 2, 3.
Cách giải: với mỗi phần tử e, lấy giá trị tuyệt đối. Nếu A[|e|] dương, đổi thành â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