หาค่ามากที่สุดใน Array หลังลบ Element ที่กำหนดใน C++

ในปัญหานี้ เราได้รับ array arr[] ขนาด n และ array del[] ขนาด m งานคือหาค่ามากที่สุดใน arr หลังลบ element ที่อยู่ใน del (ถ้ามีซ้ำ ลบแค่ตัวแรก)

ตัวอย่าง

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

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

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

ลบ element (mark INT_MAX) → sort → 取最後元素

วิธีที่ 2: Hash Map + Single Pass O(N) (แนะนำ)

1. สร้าง hash map นับจำนวนของแต่ละค่าใน del[]
2. Traverse arr[]: ถ้าค่าอยู่ใน map และ count > 0 → ลด count, ข้ามไป
3. มิฉะนั้น → อัปเดต maxVal

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

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

int findMaxAfterDelete(int arr[], int m, int del[], int n) {
    unordered_map delMap;
    for (int i = 0; i < n; i++) delMap[del[i]]++;
    
    int maxVal = INT_MIN;
    for (int i = 0; i < m; 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 {
            maxVal = max(maxVal, arr[i]);
        }
    }
    return maxVal;
}

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

ผลลัพธ์

7