Cho mảng arr[] kích thước n và mảng del[] kích thước m. Nhiệm vụ: tìm phần tử lớn nhất sau khi xóa các phần tử trong del[] khỏi arr[]. Nếu có nhiều bản sao, xóa bản sao đầu tiên.
Ví dụ minh họa
Input: arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3} Output: 7
Sau xóa: {5, 7, 2}, lớn nhất là 7.
Phương pháp 1: Xóa rồi sắp xếp O(n*m + n log n)
Đánh dấu phần tử cần xóa bằng INT_MAX, sắp xếp, lấy phần tử cuối.
Phương pháp 2: Hash Map + Max Heap O(n + m)
Lưu del[] vào hash map đếm số lần. Duyệt arr[], nếu có trong map thì giảm count, không thì push vào max-heap. Lấy top của heap.
Ví dụ chương trình (Phương pháp 2)
#include <bits/stdc++.h>
using namespace std;
int findMaxElementDelArray(int arr[], int m, int del[], int n){
unordered_map<int, int> 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()) {
if (--delMap[arr[i]] == 0) delMap.erase(arr[i]);
} else maxVal = max(maxVal, arr[i]);
}
return maxVal;
}
int main(){
int array[] = {3, 5, 1, 7, 9, 2};
int del[] = {1, 9, 3};
int m = sizeof(array)/sizeof(array[0]);
int n = sizeof(del)/sizeof(del[0]);
cout << "Phần tử lớn nhất sau xóa: " << findMaxElementDelArray(array, m, del, n);
return 0;
}
Kết quả
Phần tử lớn nhất sau xóa: 7