Kiểm tra mảng con - 5 phương pháp trong C++

Trong bài toán này, chúng ta được cho hai mảng số nguyên arr1[] và arr2[] có kích thước m và n. Nhiệm vụ là kiểm tra xem arr2 có phải là tập con của arr1 hay không.

Cả hai mảng đều không được sắp xếp và chứa các phần tử phân biệt.

Ví dụ minh họa

Input: arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1} Output: arr2 là tập con của arr1.

Phương pháp 1: Lồng vòng for (O(m*n))

Kiểm tra trực tiếp bằng vòng lặp lồng nhau: vòng ngoài duyệt arr2[], vòng trong tìm trong 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;
}

int main(){
    int arr1[] = {5, 2, 1, 6, 8, 10};
    int arr2[] = {6, 2, 1};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    isSubsetArray(arr1, arr2, m, n) ? 
        cout << "arr2[] là tập con của arr1[]" : 
        cout << "arr2[] không phải tập con của arr1[]";
    return 0;
}

Phương pháp 2: Sắp xếp + Tìm kiếm nhị phân (O(m log m + n log m))

Sắp xếp arr1[], sau đó tìm kiếm nhị phân từng phần tử của arr2[] trong arr1[].

#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;
}

Phương pháp 3: Sắp xếp cả hai mảng + Hai con trỏ (O(m log m + n log n))

Sắp xếp cả hai mảng, sau đó dùng hai chỉ số để duyệt song song.

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

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 if (arr1[j] > arr2[i]) return 0;
    }
    return (i < n) ? false : true;
}

Phương pháp 4: Bảng băm (Hashing) - O(m + n)

Tạo hash set từ arr1[], kiểm tra từng phần tử arr2[] có trong set không.

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

bool isSubsetArray(int arr1[], int arr2[], int m, int n){
    unordered_set<int> 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;
}

Phương pháp 5: Cấu trúc Set - O(m + n)

Tạo set từ arr1, ghi nhớ kích thước. Thêm các phần tử arr2, nếu kích thước không đổi thì arr2 là tập con.

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

bool isSubsetArray(int arr1[], int arr2[], int m, int n){
    unordered_set<int> 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;
}

Tất cả các phương pháp đều cho kết quả: arr2[] là tập con của arr1[]