Find All Duplicates in an Array trong C++

Cho mảng số nguyên trong phạm vi 1 ≤ a[i] ≤ n (n = kích thước mảng). Một số phần tử xuất hiện 2 lần, các phần tử khác 1 lần. Tìm tất cả phần tử xuất hiện 2 lần.

Ví dụ: [4,3,2,7,8,2,3,1] → [2,3].

Giải thuật (Dùng dấu âm index)

• Duyệt mảng:
  • x = abs(nums[i]) - 1.
  • Nếu nums[x] < 0 → x+1 là duplicate, thêm vào kết quả.
  • Ngược lại: nums[x] *= -1.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for (int x : nums) {
            int idx = abs(x) - 1;
            if (nums[idx] < 0) ans.push_back(idx + 1);
            else nums[idx] *= -1;
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {4,3,2,7,8,2,3,1};
    for (int x : ob.findDuplicates(v)) cout << x << " ";
    return 0;
}

Input

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

Output

2 3