O(n)의 배열과 C++에서 O(1) 추가 공간을 사용하여 중복 찾기

0에서 n-1까지의 숫자 목록이 있다고 가정합니다. 숫자는 가능한 한 많이 반복될 수 있습니다. 추가 공간을 차지하지 않고 반복되는 숫자를 찾아야 합니다. n =7의 값이고 목록이 [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]와 같은 경우. 답은 5, 2, 3입니다.

이 문제를 해결하려면 다음 단계를 따라야 합니다.

• 목록의 각 요소 e에 대해 다음 단계를 수행하십시오. -
  • sign :=A[e의 절대값]
  • 부호가 양수이면 음수로 만듭니다.
  • 그렇지 않으면 반복입니다.

예

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

출력

5 2 3 1