Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n, mảng del [] có kích thước m và một số nguyên k. Nhiệm vụ của chúng ta là tìm k số nhỏ nhất sau khi xóa các phần tử đã cho .
Chúng ta cần in k phần tử nhỏ nhất đầu tiên từ mảng arr [] được tìm thấy sau khi xóa tất cả các phần tử có trong mảng del []. Nếu có hai phiên bản trong mảng, hãy xóa phiên bản đầu tiên.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2
Output : 2, 5 Giải thích -
Array arr[] after deleting the elements : {5, 7, 2}
2 minimum elements are 2, 5. 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 ra k phần tử đầu tiên 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;
void findKminElementDelArray(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_MAX;
break;
}
}
}
sort(arr, arr + n);
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<<" smallest numbers after deleting the elements are ";
findKminElementDelArray(array, m, del, n, k);
return 0;
} Đầu ra
2 smallest numbers after deleting the elements are 2 5
Một cách tiếp cận khác
Một cách tiếp cận khác để giải quyết vấn đề là sử dụng hashmap và heap. Chúng tôi sẽ tạo một min-heap và một bản đồ băm. Bản đồ băm sẽ chứa tất cả các phần tử của mảng del []. Và sau đó chèn các phần tử của mảng arr [] không có trong bản đồ băm vào min-heap. Bật k phần tử từ đống và sau đó in nó.
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;
void findKminElementDelArray(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, vector<int>, greater<int> > minHeap;
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
minHeap.push(arr[i]);
}
for (int i = 0; i < k; ++i) {
cout<<minHeap.top()<<" ";
minHeap.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<<" smallest numbers after deleting the elements are ";
findKminElementDelArray(array, m, del, n, k);
return 0;
} Đầu ra
2 smallest numbers after deleting the elements are 2 5