在 C++ 中删除给定元素后查找 k 个最大数字

在这个问题中，我们给定一个大小为 n 的数组 arr[]，大小为 m 的数组 del[] 和一个整数 k。我们的任务是在删除给定元素后查找 k 个最大数字。

我们需要打印从数组 arr[] 中找到的前 k 个最大元素，这些元素是在删除 del[] 数组中存在的所有元素后找到的。如果数组中存在两个实例，则删除第一个实例。

让我们举一个例子来理解这个问题，

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 个元素。

示例

程序说明我们解决方案的工作原理

Open Compiler
#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;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

2 largest numbers after deleting the elements are 7 5

另一种方法

解决该问题的另一种方法是使用哈希表和堆。我们将创建一个最大堆和一个哈希表。哈希表将包含数组 del[] 的所有元素。然后将数组 arr[] 中不存在于哈希表中的元素插入到最大堆中。从堆中弹出 k 个元素，然后打印它。

示例

程序说明我们解决方案的工作原理

Open Compiler
#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

更新于: 2022-01-28

214 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告