数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中删除给定元素后查找k个最小数
在这个问题中，我们得到一个大小为n的数组arr[]，大小为m的数组del[]和一个整数k。我们的任务是*在删除给定元素后查找k个最小数*。
我们需要打印在删除del[]数组中存在的所有元素后找到的arr[]数组的前k个最小元素。如果数组中存在两个实例，则删除第一个实例。
让我们来看一个例子来理解这个问题：
Input : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2
Output : 2, 5**解释** −
Array arr[] after deleting the elements : {5, 7, 2}
2 minimum elements are 2, 5.解决方案方法
解决这个问题的一个简单方法是删除arr[]中所有在del[]中存在的元素。然后按升序对数组进行排序，并打印数组的前k个元素。
示例
程序说明我们解决方案的工作原理
#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;
}输出
2 smallest numbers after deleting the elements are 2 5
另一种方法
解决这个问题的另一种方法是使用哈希表和堆。我们将创建一个最小堆和一个哈希表。哈希表将包含del[]数组的所有元素。然后将不在哈希表中的arr[]数组的元素插入到最小堆中。从堆中弹出k个元素，然后打印出来。
示例
程序说明我们解决方案的工作原理
#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;
}输出
2 smallest numbers after deleting the elements are 2 5
更新于：2022年1月28日
浏览量：133
广告