หาตัวเลขที่หายไปในช่วงที่กำหนดด้วย C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ arr[] และช่วง [start, end] หาตัวเลขในช่วงที่ไม่ได้อยู่ในอาร์เรย์

ตัวอย่าง

อินพุต

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

เอาต์พุต

5, 8

วิธีแก้ปัญหา

วิธีที่ 1: Sorting + Two Pointers

เรียงอาร์เรย์ แล้วเดินพร้อมกับตัวเลขในช่วง

วิธีที่ 2: Boolean Array - O(n + range)

สร้าง bool array ขนาด range+1 mark ตัวที่มีในอาร์เรย์

วิธีที่ 3: Hash Set - O(n + range) ⭐

ใส่ทุกตัวใน unordered_set แล้วเช็คทุกตัวในช่วง

โค้ดตัวอย่าง (Hash Set)

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

void findMissingElements(int arr[], int n, int start, int end) {
    unordered_set<int> arrEle;
    for (int i = 0; i < n; i++)
        arrEle.insert(arr[i]);
    
    for (int i = start; i <= end; i++)
        if (arrEle.find(i) == arrEle.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;
}

เอาต์พุต

The missing elements are 5 8 9

สรุป

Hash Set เร็วและเข้าใจง่าย O(n + range) ใช้พื้นที่ O(n)