Dada una array de enteros, encuentre el k número más grande después de eliminar los elementos dados. En caso de elementos repetidos, elimine una instancia por cada instancia del elemento presente en la array que contiene los elementos que se eliminarán.
Suponga que quedarán al menos k elementos después de eliminar n elementos.
Ejemplos:
Entrada: array[] = { 5, 12, 33, 4, 56, 12, 20 }, del[] = { 12, 56, 5 }, k = 3
Salida: 33 20 12
Explicación: Después de eliminaciones { 33 , 4, 12, 20 } quedarán. Imprime los 3 elementos más altos de él.
Acercarse :
- Inserte todos los números en el mapa hash que se eliminarán de la array, de modo que podamos verificar si el elemento en la array también está presente en la array Eliminar en tiempo O (1).
- Atraviesa la array. Compruebe si el elemento está presente en el mapa hash.
- Si está presente, bórrelo del mapa hash.
- De lo contrario, insértelo en un montón Max.
- Después de insertar todos los elementos, excepto los que se eliminarán, extraiga k elementos del montón máximo.
C++
#include "iostream" #include "queue" #include "unordered_map" using namespace std; // Find k maximum element from arr[0..m-1] after deleting // elements from del[0..n-1] void findElementsAfterDel(int arr[], int m, int del[], int n, int k) { // Hash Map of the numbers to be deleted unordered_map<int, int> mp; for (int i = 0; i < n; ++i) { // Increment the count of del[i] mp[del[i]]++; } // Initializing the largestElement priority_queue<int> heap; for (int i = 0; i < m; ++i) { // Search if the element is present if (mp.find(arr[i]) != mp.end()) { // Decrement its frequency mp[arr[i]]--; // If the frequency becomes 0, // erase it from the map if (mp[arr[i]] == 0) mp.erase(arr[i]); } // Else compare it largestElement else heap.push(arr[i]); } // Print top k elements in the heap for (int i = 0; i < k; ++i) { cout << heap.top() << " "; // Pop the top element heap.pop(); } } int main() { int array[] = { 5, 12, 33, 4, 56, 12, 20 }; int m = sizeof(array) / sizeof(array[0]); int del[] = { 12, 56, 5 }; int n = sizeof(del) / sizeof(del[0]); int k = 3; findElementsAfterDel(array, m, del, n, k); return 0; }
Java
import java.io.*; import java.util.*; class GFG { // Find k maximum element from arr[0..m-1] after deleting // elements from del[0..n-1] static void findElementsAfterDel(int arr[], int m, int del[], int n, int k) { // Hash Map of the numbers to be deleted Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (int i = 0; i < n; ++i) { // Increment the count of del[i] if(mp.containsKey(del[i])) { mp.put(del[i], mp.get(del[i]) + 1); } else { mp.put(del[i], 1); } } // Initializing the largestElement PriorityQueue<Integer> heap = new PriorityQueue<Integer>( Collections.reverseOrder()); for (int i = 0; i < m; ++i) { // Search if the element is present if(mp.containsKey(arr[i])) { // Decrement its frequency mp.put(arr[i], mp.get(arr[i]) - 1); // If the frequency becomes 0, // erase it from the map if(mp.get(arr[i]) == 0) { mp.remove(arr[i]); } } // Else compare it largestElement else { heap.add(arr[i]); } } // Print top k elements in the heap for(int i = 0; i < k; ++i) { // Pop the top element System.out.print(heap.poll() + " "); } } // Driver code public static void main (String[] args) { int array[] = { 5, 12, 33, 4, 56, 12, 20 }; int m = array.length; int del[] = { 12, 56, 5 }; int n = del.length; int k = 3; findElementsAfterDel(array, m, del, n, k); } } // This code is contributed by rag2127
Python3
# Python3 program to find the k largest # number from the array after n deletions import math as mt import heapq # Find k maximum element from arr[0..m-1] # after deleting elements from del[0..n-1] def findElementsAfterDel(arr, m, dell, n, k): # Hash Map of the numbers to be deleted mp = dict() for i in range(n): # Increment the count of del[i] if dell[i] in mp.keys(): mp[dell[i]] += 1 else: mp[dell[i]] = 1 heap = [] for i in range(m): # Search if the element is present if (arr[i] in mp.keys()): # Decrement its frequency mp[arr[i]] -= 1 # If the frequency becomes 0, # erase it from the map if (mp[arr[i]] == 0): mp.pop(arr[i]) # else push it to heap else: heap.append(arr[i]) # creating max heap and heapifying it heapq._heapify_max(heap) # returning nlargest elements from the max heap. return heapq.nlargest(k, heap) # Driver code array = [5, 12, 33, 4, 56, 12, 20] m = len(array) dell = [12, 56, 5] n = len(dell) k = 3 print(*findElementsAfterDel(array, m, dell, n, k)) '''Code is written by RAJAT KUMAR'''
C#
using System; using System.Collections.Generic; class GFG { // Find k maximum element from arr[0..m-1] after deleting // elements from del[0..n-1] static void findElementsAfterDel(int[] arr, int m, int[] del, int n, int k) { // Hash Map of the numbers to be deleted Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < n; ++i) { // Increment the count of del[i] if(mp.ContainsKey(del[i])) { mp[del[i]]++; } else { mp.Add(del[i], 1); } } // Initializing the largestElement List<int> heap = new List<int>(); for (int i = 0; i < m; ++i) { // Search if the element is present if(mp.ContainsKey(arr[i])) { // Decrement its frequency mp[arr[i]]--; // If the frequency becomes 0, // erase it from the map if(mp[arr[i]] == 0) { mp.Remove(arr[i]); } } // Else compare it largestElement else { heap.Add(arr[i]); } } heap.Sort(); heap.Reverse(); // Print top k elements in the heap for(int i = 0; i < k; ++i) { Console.Write(heap[i] + " "); } } // Driver code static public void Main () { int[] array = { 5, 12, 33, 4, 56, 12, 20 }; int m = array.Length; int[] del = { 12, 56, 5 }; int n = del.Length; int k = 3; findElementsAfterDel(array, m, del, n, k); } } // This code is contributed by avanitrachhadiya2155
Javascript
<script> // Find k maximum element from arr[0..m-1] after deleting // elements from del[0..n-1] function findElementsAfterDel(arr,m,del,n,k) { // Hash Map of the numbers to be deleted let mp = new Map(); for (let i = 0; i < n; ++i) { // Increment the count of del[i] if(mp.has(del[i])) { mp.set(del[i], mp.get(del[i]) + 1); } else { mp.set(del[i], 1); } } // Initializing the largestElement let heap =[]; for (let i = 0; i < m; ++i) { // Search if the element is present if(mp.has(arr[i])) { // Decrement its frequency mp.set(arr[i], mp.get(arr[i]) - 1); // If the frequency becomes 0, // erase it from the map if(mp.get(arr[i]) == 0) { mp.delete(arr[i]); } } // Else compare it largestElement else { heap.push(arr[i]); } } heap.sort(function(a,b){return b-a;}); // Print top k elements in the heap for(let i = 0; i < k; ++i) { // Pop the top element document.write(heap[i] + " "); } } // Driver code let array=[ 5, 12, 33, 4, 56, 12, 20 ]; let m = array.length; let del=[12, 56, 5]; let n = del.length; let k = 3; findElementsAfterDel(array, m, del, n, k); // This code is contributed by unknown2108 </script>
33 20 12
Complejidad temporal: O(m + n)
Espacio Auxiliar: O(m + n)
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA