ตรวจสอบว่า Array หนึ่งเป็น Subset ของอีก Array หนึ่งใน C++ (5 วิธี)

ในปัญหานี้ เราได้รับอาร์เรย์สองอาร์เรย์ arr1[] และ arr2[] ขนาด m และ n งานของเราคือการตรวจสอบว่า arr2 เป็น subset ของ arr1 หรือไม่ ทั้งสองอาร์เรย์ไม่ได้เรียงลำดับและมีค่าที่ไม่ซ้ำกัน

ตัวอย่างเพื่อเข้าใจปัญหา

Input: arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1} Output: arr2 is a subset of arr1

วิธีที่ 1: ใช้ Nested Loop (O(m*n))

ตรวจสอบแต่ละ element ของ arr2 ว่ามีใน arr1 หรือไม่

#include <iostream>
using namespace std;

bool isSubsetArray(int arr1[], int arr2[], int m, int n) {
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (arr2[i] == arr1[j]) break;
        }
        if (j == m) return false;
    }
    return true;
}

วิธีที่ 2: เรียงลำดับ + Binary Search (O(m log m + n log m))

เรียง arr1 แล้วค้นหาแต่ละ element ของ arr2 ด้วย binary search

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

int binarySearch(int arr[], int low, int high, int x) {
    if (high >= low) {
        int mid = (low + high) / 2;
        if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x)) return mid;
        else if (x > arr[mid]) return binarySearch(arr, mid + 1, high, x);
        else return binarySearch(arr, low, mid - 1, x);
    }
    return -1;
}

bool isSubsetArray(int arr1[], int arr2[], int m, int n) {
    sort(arr1, arr1 + m);
    for (int i = 0; i < n; i++) {
        if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1) return 0;
    }
    return 1;
}

วิธีที่ 3: เรียงลำดับทั้งคู่ + Two Pointer (O(m log m + n log n))

เรียงทั้งสองอาร์เรย์ แล้วใช้ two pointer เปรียบเทียบ

bool isSubsetArray(int arr1[], int arr2[], int m, int n) {
    if (m < n) return 0;
    sort(arr1, arr1 + m);
    sort(arr2, arr2 + n);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (arr1[j] < arr2[i]) j++;
        else if (arr1[j] == arr2[i]) { j++; i++; }
        else return 0;
    }
    return (i < n) ? false : true;
}

วิธีที่ 4: ใช้ Hashing (O(m + n))

สร้าง hash table จาก arr1 แล้วค้นหา element ของ arr2

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

bool isSubsetArray(int arr1[], int arr2[], int m, int n) {
    set arr1Hash;
    for (int i = 0; i < m; i++) arr1Hash.insert(arr1[i]);
    for (int i = 0; i < n; i++) {
        if (arr1Hash.find(arr2[i]) == arr1Hash.end()) return false;
    }
    return true;
}

วิธีที่ 5: ใช้ Set Data Structure (O(m + n))

สร้าง set จาก arr1 แล้ว insert arr2 ดูว่า size เปลี่ยนหรือไม่

bool isSubsetArray(int arr1[], int arr2[], int m, int n) {
    unordered_set arrSet;
    for (int i = 0; i < m; i++) arrSet.insert(arr1[i]);
    int setSize = arrSet.size();
    for (int i = 0; i < n; i++) arrSet.insert(arr2[i]);
    return arrSet.size() == setSize;
}

ผลลัพธ์

arr2[] is subset of arr1[]