Dada una array de enteros, encuentre los k números más pequeños después de eliminar los elementos dados. En caso de elementos repetidos, elimine solo una instancia en la array dada por cada instancia del elemento presente en la array que contiene los elementos que se eliminarán.
Suponga que quedan al menos k elementos en la array después de realizar n eliminaciones.
Ejemplos:
Entrada: array[] = { 5, 12, 33, 4, 56, 12, 20 }, del[] = { 12, 56, 5 }, k = 3 Salida: 4 12 20 Explicación: después de eliminaciones { 33
,
4 , 12, 20 } quedarán. Imprime los 3 elementos más pequeños de la parte superior.
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 mínimo.
- Después de insertar todos los elementos, excepto los que se eliminarán, extraiga k elementos del montón mínimo.
C++
#include "iostream"
#include "queue"
#include "unordered_map"
#include "vector"
using namespace std;
// Find k minimum 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]]++;
}
priority_queue<int, vector<int>, greater<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 push it in the min heap
else
heap.push(arr[i]);
}
// Print top k elements in the min 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
// Java program to find the k maximum
// number from the array after n deletions
import java.util.*;
public class GFG
{
// Find k minimum 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
HashMap<Integer, Integer> mp = new HashMap<>();
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);
}
}
Vector<Integer> heap = new Vector<Integer>();
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 push it in the min heap
else
heap.add(arr[i]);
}
Collections.sort(heap);
// Print top k elements in the min heap
for (int i = 0; i < k; ++i)
{
System.out.print(heap.get(0) + " ");
// Pop the top element
heap.remove(0);
}
}
// 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 divvyeshrabadiya07.
Python3
# Python3 program to find the k maximum # 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 min heap and heapifying it heapq.heapify(heap) # retuurning nsmallest elements from the min heap. return heapq.nsmallest(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#
// C# program to find the k maximum
// number from the array after n deletions
using System;
using System.Collections.Generic;
class GFG
{
// Find k minimum 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[del[i]] = 1;
}
}
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 push it in the min heap
else
heap.Add(arr[i]);
}
heap.Sort();
// Print top k elements in the min heap
for (int i = 0; i < k; ++i)
{
Console.Write(heap[0] + " ");
// Pop the top element
heap.RemoveAt(0);
}
}
// Driver code
static 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 divyesh072019.
Javascript
<script>
// JavaScript program to find the k maximum
// number from the array after n deletions
// Find k minimum 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);
}
}
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 push it in the min heap
else
heap.push(arr[i]);
}
heap.sort(function(a,b){return a-b;});
// Print top k elements in the min heap
for (let i = 0; i < k; ++i)
{
document.write(heap[0] + " ");
// Pop the top element
heap.splice(0,1);
}
}
// 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>
Producción:
4 12 20
Complejidad de tiempo: O(M*log(M)), ya que insertar en una cola de prioridad es una operación logarítmica y lo estamos haciendo M veces en el peor de los casos, donde M es el tamaño de la array.
Espacio auxiliar: O(M + N), donde M y N representan el tamaño de las dos arrays dadas.
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA