หา Union และ Intersection ของอาร์เรย์ไม่เรียงลำดับใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา Union (ยูเนียน) และ Intersection (อินเตอร์เซกชัน) ของอาร์เรย์ 2 ชุดที่ไม่ได้เรียงลำดับ

ตัวอย่าง

Input: arr_one = [1, 2, 3, 4, 5], arr_two = [3, 4, 5, 6, 7]
Output: Union: 1 2 3 4 5 6 7, Intersection: 3 4 5

ขั้นตอนการแก้ปัญหา

Union

1. สร้างอาร์เรย์ union_result ว่าง
2. เพิ่มทุกสมาชิกจาก arr_one
3. เพิ่มสมาชิกจาก arr_two ก็ต่อเมื่อไม่มีอยู่ใน union_result แล้ว

Intersection

1. สร้างอาร์เรย์ intersection_result ว่าง
2. วนลูป arr_one เพิ่มสมาชิกก็ต่อเมื่อมีอยู่ใน arr_two ด้วย

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

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

bool isElementPresentInArray(int arr[], int arr_length, int element) {
    for (int i = 0; i < arr_length; ++i) {
        if (arr[i] == element) return true;
    }
    return false;
}

void findUnionAndIntersection(int arr_one[], int arr_one_length, int arr_two[], int arr_two_length) {
    // Union
    int union_result[arr_one_length + arr_two_length] = {};
    for (int i = 0; i < arr_one_length; ++i) {
        union_result[i] = arr_one[i];
    }
    int union_index = arr_one_length;
    for (int i = 0; i < arr_two_length; ++i) {
        if (!isElementPresentInArray(arr_one, arr_one_length, arr_two[i])) {
            union_result[union_index++] = arr_two[i];
        }
    }
    cout << "Union: ";
    for (int i = 0; i < union_index; ++i) cout << union_result[i] << " ";
    cout << endl;
    
    // Intersection
    int intersection_result[arr_one_length + arr_two_length] = {};
    int intersection_index = 0;
    for (int i = 0; i < arr_one_length; ++i) {
        if (isElementPresentInArray(arr_two, arr_two_length, arr_one[i])) {
            intersection_result[intersection_index++] = arr_one[i];
        }
    }
    cout << "Intersection: ";
    for (int i = 0; i < intersection_index; ++i) cout << intersection_result[i] << " ";
    cout << endl;
}

int main() {
    int arr_one[] = {1, 2, 3, 4, 5};
    int arr_two[] = {3, 4, 5, 6, 7};
    findUnionAndIntersection(arr_one, 5, arr_two, 5);
    return 0;
}

ผลลัพธ์

Union: 1 2 3 4 5 6 7
Intersection: 3 4 5

หมายเหตุ: โค้ดต้นฉบับมีบั๊ก

ในส่วน Intersection โค้ดต้นฉบับตรวจสอบ arr_two[i] แทนที่จะเป็น arr_one[i] โค้ดข้างต้นแก้ไขแล้ว

วิธีที่ดีกว่า (ใช้ STL)

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

void findUnionAndIntersectionSTL(vector& a, vector& b) {
    set s(a.begin(), a.end());
    s.insert(b.begin(), b.end());
    cout << "Union: ";
    for (int x : s) cout << x << " ";
    cout << endl;
    
    set sa(a.begin(), a.end());
    cout << "Intersection: ";
    for (int x : b) if (sa.count(x)) cout << x << " ";
    cout << endl;
}

สรุป

Union = ทุกค่าที่ปรากฏในอาร์เรย์ใดอาร์เรย์หนึ่ง, Intersection = ค่าที่ปรากฏในทั้งสองอาร์เรย์ ใช้ STL set/unordered_set จะง่ายและเร็วกว่า (O(n log n) หรือ O(n)) หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ