Trong bài toán này, chúng ta được đưa ra một mảng aar [] có kích thước n và một mảng del [] khác có kích thước m. Nhiệm vụ của chúng ta là tìm giá trị lớn nhất sau khi xóa các phần tử đã cho. Nếu yêu cầu xóa một phần tử có nhiều phiên bản, hãy xóa phiên bản đầu tiên của phần tử đó.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}
Output : 7 Giải thích -
Array arr[] after deleting the elements : {5, 7, 2}
Largest element of the array is 7 Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là xóa tất cả các phần tử khỏi arr [] có trong del []. Sau đó, sắp xếp mảng theo thứ tự tăng dần và in phần tử cuối cùng của mảng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The largest element after deleting the elements is 7
Cách tiếp cận khác
Một giải pháp cho vấn đề là sử dụng bản đồ băm để kiểm tra việc xóa. Chúng tôi sẽ lưu trữ các phần tử của mảng del [] vào một bản đồ băm và đối với mỗi phần tử của arr [] hãy kiểm tra sự hiện diện của nó trong bản đồ băm. Nếu nó hiện diện, hãy xóa phần tử khỏi bản đồ băm, nếu không, hãy kiểm tra xem nó có phải là giá trị lớn nhất hay không bằng cách so sánh nó với maxVal. Nếu có, hãy lưu trữ nó vào maxVal. Sau khi toàn bộ mảng arr [] được duyệt, in maxVal là giá trị lớn nhất sau khi xóa các phần tử.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The largest element after deleting the elements is 7