หา 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: 7, 5

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

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

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

คล้ายวิธีหา K smallest แต่ใช้ max-heap แทน

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

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

void findKMaxAfterDelete(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 maxHeap;
    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 maxHeap.push(arr[i]);
    }
    
    for (int i = 0; i < k; i++) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
}

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

ผลลัพธ์

7 5