ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n อาร์เรย์ del[] ของขนาด m และจำนวนเต็ม k งานของเราคือ หาจำนวนที่มากที่สุด k หลังจากลบองค์ประกอบที่กำหนด .
เราจำเป็นต้องพิมพ์องค์ประกอบที่ใหญ่ที่สุด k รายการแรกจากอาร์เรย์ arr[] ที่พบหลังจากลบองค์ประกอบทั้งหมดที่มีอยู่ในอาร์เรย์ del[] หากมี 2 อินสแตนซ์ในอาร์เรย์ ให้ลบอินสแตนซ์แรกออก
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2
Output : 7, 5 คำอธิบาย −
Array arr[] after deleting the elements : {5, 7, 2}
2 maximum elements are 7, 5. แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการลบองค์ประกอบทั้งหมดออกจาก arr[] ที่มีอยู่ใน del[] จากนั้นเรียงลำดับอาร์เรย์จากมากไปหาน้อยและพิมพ์องค์ประกอบ k อันดับแรกของอาร์เรย์
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
void findKmaxElementDelArray(int arr[], int n, int del[], int m, int k){
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(arr[j] == del[i]){
arr[j] = INT_MIN;
break;
}
}
}
sort(arr, arr + n, greater<int>());
for (int i = 0; i < k; ++i) {
cout<<arr[i]<<" ";
}
}
int main(){
int array[] = { 3, 5, 1, 7, 9, 2 };
int m = sizeof(array) / sizeof(array[0]);
int del[] = { 1, 9, 3 };
int n = sizeof(del) / sizeof(del[0]);
int k = 2;
cout<<k<<" largest numbers after deleting the elements are ";
findKmaxElementDelArray(array, m, del, n, k);
return 0;
} ผลลัพธ์
2 largest numbers after deleting the elements are 7 5
แนวทางอื่น
อีกแนวทางหนึ่งในการแก้ปัญหาคือการใช้ hashmap และ heap เราจะสร้าง max-heap และ hash map hashmap จะมีองค์ประกอบทั้งหมดของอาร์เรย์ del[] จากนั้นแทรกองค์ประกอบของอาร์เรย์ arr[] ที่ไม่มีอยู่ใน hash-map ไปยัง max-heap ป๊อปองค์ประกอบ k จากฮีปแล้วพิมพ์
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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()) {
deleteElement[arr[i]]--;
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 m = sizeof(array) / sizeof(array[0]);
int del[] = { 1, 9, 3 };
int n = sizeof(del) / sizeof(del[0]);
int k = 2;
cout<<k<<" largest numbers after deleting the elements are ";
findKmaxElementDelArray(array, m, del, n, k);
return 0;
} ผลลัพธ์
2 largest numbers after deleting the elements are 7 5
