Hợp và giao của hai mảng chưa sắp xếp C++

Cho 2 mảng chưa sắp xếp, tìm Union (hợp) và Intersection (giao).

• Union: tất cả phần tử xuất hiện ít nhất ở 1 mảng (không trùng).
• Intersection: phần tử xuất hiện ở cả 2 mảng.

Cách 1: Dùng unordered_set (O(n+m))

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

int main() {
    vector A = {1,2,3,4}, B = {5,3,4};
    
    unordered_set sA(A.begin(), A.end());
    unordered_set sB(B.begin(), B.end());
    
    // Union
    unordered_set uni = sA;
    uni.insert(sB.begin(), sB.end());
    
    // Intersection
    vector inter;
    for (int x : sA) if (sB.count(x)) inter.push_back(x);
    
    cout << "Union: "; for (int x : uni) cout << x << " ";
    cout << "\nIntersection: "; for (int x : inter) cout << x << " ";
    return 0;
}

Cách 2: Sắp xếp + 2 con trỏ (O(n log n), không dùng extra space nhiều)

vector unionSorted(vector A, vector B) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    vector res;
    int i=0, j=0;
    while (i interSorted(vector A, vector B) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    vector res;
    int i=0, j=0;
    while (i
Kết quả
Union: 1 2 3 4 5
Intersection: 3 4