หา K ตัวเลขน้อยที่สุดหลังลบ Element ที่กำหนดใน C++

ในปัญหานี้ เราได้รับ arr[], del[], และ K งานคือหา K ตัวเลขน้อยที่สุดใน arr หลังลบ element ที่อยู่ใน del

ตัวอย่าง

Input: arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2 Output: 2, 5

หลังลบ: {5, 7, 2} → 2 smallest: 2, 5

วิธีที่ 1: Brute Force + Sort O(N log N)

ลบ element (mark INT_MAX) → sort → 取前 K 元素

วิธีที่ 2: Hash Map + Min Heap O(N + K log N) (แนะนำ)

1. สร้าง hash map นับ count ของ del[]
2. สร้าง min-heap ใส่ element ของ arr[] ที่ไม่อยู่ใน del map
3. Pop K ครั้งจาก heap

ตัวอย่างโค้ด (วิธีที่ 2)

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

void findKMinAfterDelete(int arr[], int n, int del[], int m, int k) {
    unordered_map delMap;
    for (int i = 0; i < m; i++) delMap[del[i]]++;
    
    priority_queue, greater> minHeap;
    for (int i = 0; i < n; i++) {
        if (delMap.find(arr[i]) != delMap.end() && delMap[arr[i]] > 0) {
            delMap[arr[i]]--;
            if (delMap[arr[i]] == 0) delMap.erase(arr[i]);
        } else minHeap.push(arr[i]);
    }
    
    for (int i = 0; i < k; i++) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
}

int main() {
    int arr[] = {3, 5, 1, 7, 9, 2};
    int del[] = {1, 9, 3};
    findKMinAfterDelete(arr, 6, del, 3, 2); // 2 5
    return 0;
}

ผลลัพธ์

2 5