Tìm tất cả các bản sao trong một mảng trong C ++

Giả sử chúng ta có một mảng các số nguyên, trong phạm vi 1 ≤ a [i] ≤ n (n =kích thước của mảng), ở đây một số phần tử xuất hiện hai lần và một số phần tử khác xuất hiện một lần. Chúng ta phải tìm tất cả các phần tử xuất hiện hai lần trong mảng này. Vì vậy, nếu mảng là [4,3,2,7,8,2,3,1], thì đầu ra sẽ là [2, 3]

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

• n:=kích thước của mảng, tạo một mảng được gọi là ans
• cho tôi trong phạm vi từ 0 đến n - 1
  • x:=giá trị tuyệt đối của nums [i]
  • giảm x đi 1
  • nếu nums [x] <0, thì thêm x + 1 vào ans, nếu không nums [x]:=nums [x] * (-1)
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

[2,3]