หา Relative Complement (Set Difference) ของอาร์เรย์เรียงลำดับสองอันใน C++

Relative Complement ของ A และ B = องค์ประกอบที่อยู่ใน A แต่ไม่อยู่ใน B (A - B)

ตัวอย่าง: A = [3, 6, 10, 12, 15], B = [1, 3, 5, 10, 16] → ผลลัพธ์ = [6, 12, 15]

ใช้ STL set_difference

ต้องการอาร์เรย์เรียงลำดับก่อน (หรือเรียงในโค้ด)

ตัวอย่างโค้ด

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int first[] = {3, 6, 10, 12, 15};
    int second[] = {1, 3, 5, 10, 16};
    int n = 5;

    vector temp(n);
    vector::iterator it, ls;

    sort(first, first + n);
    sort(second, second + n);

    cout << "First array: ";
    for (int i = 0; i < n; i++) cout << first[i] << " ";
    cout << endl;

    cout << "Second array: ";
    for (int i = 0; i < n; i++) cout << second[i] << " ";
    cout << endl;

    ls = set_difference(first, first + n, second, second + n, temp.begin());

    cout << "Relative complement (A - B): ";
    for (it = temp.begin(); it != ls; ++it)
        cout << *it << " ";
    cout << endl;

    return 0;
}

ผลลัพธ์

First array: 3 6 10 12 15
Second array: 1 3 5 10 16
Relative complement (A - B): 6 12 15

หมายเหตุ

• set_difference ต้องการ Range ที่เรียงลำดับแล้ว
• ผลลัพธ์เก็บใน temp ใช้ Iterator ls บอกจุดสิ้นสุดจริง
• Complexity: O(m + n)

สำหรับ Unsorted Array

unordered_set setB(second, second + n);
vector result;
for (int x : first)
    if (!setB.count(x)) result.push_back(x);
// O(m + n) เฉลี่ย แต่ไม่คงลำดับ