Tìm các phần tử thiếu trong một khoảng trong C++

Giới thiệu

Cho mảng arr[] và khoảng [start, end]. Tìm các số trong khoảng không xuất hiện trong mảng.

Ví dụ minh họa

Đầu vào

arr[] = {4, 6, 3, 7}, start = 3, end = 8

Đầu ra

5, 8

Giải thích

Khoảng [3,8]: 3,4,5,6,7,8
Mảng: 4,6,3,7
Thiếu: 5, 8

Phương pháp 1: Sắp xếp và con trỏ - O(n log n)

Sắp xếp mảng, dùng lower_bound tìm vị trí bắt đầu, duyệt song song mảng và khoảng.

Chương trình minh họa

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

void findMissingElements(int arr[], int n, int low, int high) {
    sort(arr, arr + n);
    int* ptr = lower_bound(arr, arr + n, low);
    int idx = ptr - arr;
    int x = low;
    while (idx < n && x <= high) {
        if (arr[idx] != x)
            cout << x << " ";
        else
            idx++;
        x++;
    }
    while (x <= high)
        cout << x++ << " ";
}

int main() {
    int arr[] = {4, 6, 3, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    int low = 3, high = 9;
    cout << "The missing elements are ";
    findMissingElements(arr, n, low, high);
    return 0;
}

Đầu ra

The missing elements are 5 8 9

Phương pháp 2: Mảng boolean - O(n + range)

Tạo mảng bool kích thước (end-start+1), đánh dấu các phần tử có trong mảng, in những vị trí false.

Chương trình minh họa

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

void findMissingElements(int arr[], int n, int start, int end) {
    vector present(end - start + 1, false);
    for (int i = 0; i < n; i++)
        if (start <= arr[i] && arr[i] <= end)
            present[arr[i] - start] = true;
    for (int i = 0; i <= end - start; i++)
        if (!present[i])
            cout << (start + i) << "\t";
}

int main() {
    int arr[] = {4, 6, 3, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    int low = 3, high = 9;
    cout << "The missing elements are ";
    findMissingElements(arr, n, low, high);
    return 0;
}

Đầu ra

The missing elements are 5 8 9

Phương pháp 3: Bảng băm (Hash Set) - O(n) trung bình

Cho tất cả phần tử mảng vào unordered_set, kiểm tra từng số trong khoảng.

Chương trình minh họa

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

void findMissingElements(int arr[], int n, int start, int end) {
    unordered_set s(arr, arr + n);
    for (int i = start; i <= end; i++)
        if (s.find(i) == s.end())
            cout << i << "\t";
}

int main() {
    int arr[] = {4, 6, 3, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    int low = 3, high = 9;
    cout << "The missing elements are ";
    findMissingElements(arr, n, low, high);
    return 0;
}

Đầu ra

The missing elements are 5 8 9