Dada una array arr[] de tamaño N , la tarea es encontrar el recuento mínimo de elementos de la array necesarios para eliminar de modo que la frecuencia de cada elemento de la array sea igual a su valor
Ejemplos:
Entrada: arr[] = { 2, 4, 1, 4, 2 }
Salida: 2
Explicación:
Eliminar arr[1] de la array modifica arr[] a { 2, 1, 4, 2 }
Eliminar arr[2] de la array modifica arr[] a { 2, 1, 2 }
Elementos distintos en la array son: { 1, 2 } con frecuencias 1 y 2 respectivamente.
Por lo tanto, la salida requerida es 2.Entrada: arr[] = { 2, 7, 1, 8, 2, 8, 1, 8 }
Salida: 5
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa , digamos, mp para almacenar la frecuencia de cada elemento distinto de la array.
- Atraviese la array y almacene la frecuencia de cada elemento distinto de la array .
- Inicialice una variable, por ejemplo, cntMinRem para almacenar el recuento mínimo de elementos de array necesarios para eliminar, de modo que la frecuencia de arr[i] sea igual a arr[i] .
- Recorra el mapa usando el valor clave del mapa como i y verifique las siguientes condiciones:
- Si mp[i] < i , actualice el valor de cntMinRem += mp[i] .
- Si mp[i] > i , actualice el valor de cntMinRem += (mp[i] – i) .
- Finalmente, imprima el valor de cntMinRem .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum count of
// elements required to be removed such
// that frequency of arr[i] equal to arr[i]
int min_elements(int arr[], int N)
{
// Stores frequency of each
// element of the array
unordered_map<int, int> mp;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency
// of arr[i]
mp[arr[i]]++;
}
// Stores minimum count of removals
int cntMinRem = 0;
// Traverse the map
for (auto it : mp) {
// Stores key value
// of the map
int i = it.first;
// If frequency of i is
// less than i
if (mp[i] < i) {
// Update cntMinRem
cntMinRem += mp[i];
}
// If frequency of i is
// greater than i
else if (mp[i] > i) {
// Update cntMinRem
cntMinRem += (mp[i] - i);
}
}
return cntMinRem;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 1, 4, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << min_elements(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the minimum count of
// elements required to be removed such
// that frequency of arr[i] equal to arr[i]
public static int min_elements(int arr[], int N)
{
// Stores frequency of each
// element of the array
Map<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update frequency
// of arr[i]
mp.put(arr[i],
mp.getOrDefault(arr[i], 0) + 1);
}
// Stores minimum count of removals
int cntMinRem = 0;
// Traverse the map
for(int key : mp.keySet())
{
// Stores key value
// of the map
int i = key;
int val = mp.get(i);
// If frequency of i is
// less than i
if (val < i)
{
// Update cntMinRem
cntMinRem += val;
}
// If frequency of i is
// greater than i
else if (val > i)
{
// Update cntMinRem
cntMinRem += (val - i);
}
}
return cntMinRem;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 4, 1, 4, 2 };
System.out.println(min_elements(
arr, arr.length));
}
}
// This code is contributed by grand_master
Python3
# Python3 program to implement
# the above approach
# Function to find the minimum count of
# elements required to be removed such
# that frequency of arr[i] equal to arr[i]
def min_elements(arr, N) :
# Stores frequency of each
# element of the array
mp = {};
# Traverse the array
for i in range(N) :
# Update frequency
# of arr[i]
if arr[i] in mp :
mp[arr[i]] += 1;
else :
mp[arr[i]] = 1;
# Stores minimum count of removals
cntMinRem = 0;
# Traverse the map
for it in mp :
# Stores key value
# of the map
i = it;
# If frequency of i is
# less than i
if (mp[i] < i) :
# Update cntMinRem
cntMinRem += mp[i];
# If frequency of i is
# greater than i
elif (mp[i] > i) :
# Update cntMinRem
cntMinRem += (mp[i] - i);
return cntMinRem;
# Driver Code
if __name__ == "__main__" :
arr = [ 2, 4, 1, 4, 2 ];
N = len(arr);
print(min_elements(arr, N));
# This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum count of
// elements required to be removed such
// that frequency of arr[i] equal to arr[i]
static int min_elements(int[] arr, int N)
{
// Stores frequency of each
// element of the array
Dictionary<int, int> mp = new Dictionary<int, int>();
// Traverse the array
for (int i = 0; i < N; i++)
{
// Update frequency
// of arr[i]
if(mp.ContainsKey(arr[i]))
{
mp[arr[i]]++;
}
else
{
mp[arr[i]] = 1;
}
}
// Stores minimum count of removals
int cntMinRem = 0;
// Traverse the map
foreach (KeyValuePair<int, int> it in mp)
{
// Stores key value
// of the map
int i = it.Key;
// If frequency of i is
// less than i
if (mp[i] < i)
{
// Update cntMinRem
cntMinRem += mp[i];
}
// If frequency of i is
// greater than i
else if (mp[i] > i)
{
// Update cntMinRem
cntMinRem += (mp[i] - i);
}
}
return cntMinRem;
}
// Driver code
static void Main()
{
int[] arr = { 2, 4, 1, 4, 2 };
int N = arr.Length;
Console.Write(min_elements(arr, N));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the minimum count of
// elements required to be removed such
// that frequency of arr[i] equal to arr[i]
function min_elements(arr, N)
{
// Stores frequency of each
// element of the array
var mp = new Map();
// Traverse the array
for (var i = 0; i < N; i++) {
// Update frequency
// of arr[i]
if(mp.has(arr[i]))
{
mp.set(arr[i], mp.get(arr[i])+1);
}
else
{
mp.set(arr[i], 1);
}
}
// Stores minimum count of removals
var cntMinRem = 0;
// Traverse the map
mp.forEach((value, key) => {
// Stores key value
// of the map
var i = key;
// If frequency of i is
// less than i
if (mp.get(i) < i) {
// Update cntMinRem
cntMinRem += mp.get(i);
}
// If frequency of i is
// greater than i
else if (mp.get(i) > i) {
// Update cntMinRem
cntMinRem += (mp.get(i) - i);
}
});
return cntMinRem;
}
// Driver Code
var arr = [2, 4, 1, 4, 2];
var N = arr.length;
document.write( min_elements(arr, N));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA