Tìm các bản sao trong O (n) thời gian và O (1) không gian thừa - Đặt 1 trong C ++

Giả sử chúng ta có một danh sách các số từ 0 đến n-1. Một số có thể được lặp lại nhiều lần nhất có thể. Chúng ta phải tìm các số lặp lại mà không chiếm thêm bất kỳ khoảng trống nào. Nếu giá trị của n =7, và danh sách giống như [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]. Câu trả lời sẽ là 5, 2, 3.

Để giải quyết vấn đề này, chúng ta phải làm theo các bước sau -

đối với mỗi phần tử e trong danh sách, hãy thực hiện các bước sau -

• dấu hiệu:=A [giá trị tuyệt đối của e]
• nếu dấu hiệu là số dương, thì hãy đặt dấu hiệu là số âm
• Nếu không thì đó là sự lặp lại.

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);
}

Đầu ra

5 2 3 1