Tìm k số lớn nhất sau khi xóa các phần tử đã cho trong C ++

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ố lớn nhất sau khi xóa các phần tử đã cho .

Chúng ta cần in k phần tử lớn 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 : 7, 5

Giải thích -

Array arr[] after deleting the elements : {5, 7, 2}
2 maximum elements are 7, 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ự giảm 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 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;
}

Đầu ra

2 largest numbers after deleting the elements are 7 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 đống tối đa 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 vùng tối đa. 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 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;
}

Đầu ra

2 largest numbers after deleting the elements are 7 5