O(n) 시간 및 O(1) 추가 공간에서 중복 찾기 - C++에서 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