Cho mảng arr[] kích thước n, mảng del[] kích thước m, và số k. Nhiệm vụ: tìm k số lớn nhất sau khi xóa các phần tử trong del[] khỏi arr[].
Ví dụ minh họa
Input: arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2 Output: 7, 5
Sau xóa: {5, 7, 2}, 2 số lớn nhất: 7, 5.
Phương pháp 1: Xóa, sắp xếp giảm dần, lấy k đầu
Đánh dấu xóa bằng INT_MIN, sort greater, in k phần tử đầu.
Phương pháp 2: Hash Map + Max Heap
Hash map lưu del[], duyệt arr[] push vào max-heap nếu không bị xóa, pop k lần.
Ví dụ chương trình (Phương pháp 2)
#include <bits/stdc++.h>
using namespace std;
void findKmaxElementDelArray(int arr[], int n, int del[], int m, int k){
unordered_map<int, int> deleteElement;
for (int i = 0; i < m; ++i) deleteElement[del[i]]++;
priority_queue<int> maxHeap;
for (int i = 0; i < n; ++i) {
if (deleteElement.find(arr[i]) != deleteElement.end()) {
if (--deleteElement[arr[i]] == 0) deleteElement.erase(arr[i]);
} else maxHeap.push(arr[i]);
}
for (int i = 0; i < k; ++i) {
cout << maxHeap.top() << " ";
maxHeap.pop();
}
}
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]);
int k = 2;
cout << k << " số lớn nhất sau xóa: ";
findKmaxElementDelArray(array, m, del, n, k);
return 0;
}
Kết quả
2 số lớn nhất sau xóa: 7 5