C++에서 배열의 모든 중복 찾기

1 ≤ a[i] ≤ n(n =배열의 크기) 범위의 정수 배열이 있다고 가정합니다. 여기서 일부 요소는 두 번 나타나고 다른 요소는 한 번 나타납니다. 이 배열에서 두 번 나타나는 모든 요소를 ​​찾아야 합니다. 따라서 배열이 [4,3,2,7,8,2,3,1]이면 출력은 [2, 3]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=배열의 크기, 하나의 배열을 다음과 같이
• 0 ~ n – 1 범위의 i에 대해
  • x :=nums[i]의 절대값
  • x 1 감소
  • nums[x] <0이면 x + 1을 ans에 추가하고, 그렇지 않으면 nums[x] :=nums[x] * (-1)
• 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> findDuplicates(vector<int>& nums) {
      int n = nums.size();
      vector <int> ans;
      for(int i = 0; i < n; i++){
         int x = abs(nums[i]);
         x--;
         if(nums[x] < 0) ans.push_back(x + 1);
         else nums[x] *= -1;
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {4,3,2,7,8,2,3,1};
   print_vector(ob.findDuplicates(v));
}

입력

[4,3,2,7,8,2,3,1]

출력

[2,3]