資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 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 個元素。
示例
程式說明我們解決方案的工作原理
#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;
}輸出
2 largest numbers after deleting the elements are 7 5
另一種方法
解決該問題的另一種方法是使用雜湊表和堆。我們將建立一個最大堆和一個雜湊表。雜湊表將包含陣列 del[] 的所有元素。然後將陣列 arr[] 中不存在於雜湊表中的元素插入到最大堆中。從堆中彈出 k 個元素，然後列印它。
示例
程式說明我們解決方案的工作原理
#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 次檢視
廣告