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