Dada una array arr[] de N enteros, la tarea es encontrar las eliminaciones mínimas requeridas para que la frecuencia de arr[i] sea exactamente arr[i] en la array para todos los valores posibles de i .
Ejemplos:
Entrada: arr[] = {1, 2, 2, 3, 3}
Salida: 2
Frecuencia (1) = 1
Frecuencia (2) = 2
Frecuencia (3) = 2, la frecuencia no se puede aumentar
Entonces, elimine cada aparición de 3.
Entrada: arr[] = {2, 3, 2, 3, 4, 4, 4, 4, 5}
Salida: 3
Planteamiento: Hay dos casos:
- Si la frecuencia de X es mayor o igual a X, eliminamos las frecuencias adicionales de X para obtener exactamente X elementos de valor X.
- Si la frecuencia de X es menor que X, eliminamos todas las apariciones de X, ya que es imposible obtener un elemento adicional del valor X.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum
// deletions required
int MinDeletion(int a[], int n)
{
// To store the frequency of
// the array elements
unordered_map<int, int> map;
// Store frequency of each element
for (int i = 0; i < n; i++)
map[a[i]]++;
// To store the minimum deletions required
int ans = 0;
for (auto i : map) {
// Value
int x = i.first;
// It's frequency
int frequency = i.second;
// If number less than or equal
// to it's frequency
if (x <= frequency) {
// Delete extra occurrences
ans += (frequency - x);
}
// Delete every occurrence of x
else
ans += frequency;
}
return ans;
}
// Driver code
int main()
{
int a[] = { 2, 3, 2, 3, 4, 4, 4, 4, 5 };
int n = sizeof(a) / sizeof(a[0]);
cout << MinDeletion(a, n);
return 0;
}
Java
// Java Implementation of above approach
import java.util.*;
class GFG
{
// Function to return the minimum
// deletions required
static int MinDeletion(int a[], int n)
{
// To store the frequency of
// the array elements
Map<Integer,Integer> mp = new HashMap<>();
// Store frequency of each element
for (int i = 0 ; i < n; i++)
{
if(mp.containsKey(a[i]))
{
mp.put(a[i], mp.get(a[i])+1);
}
else
{
mp.put(a[i], 1);
}
}
// To store the minimum deletions required
int ans = 0;
for (Map.Entry<Integer,Integer> i : mp.entrySet())
{
// Value
int x = i.getKey();
// It's frequency
int frequency = i.getValue();
// If number less than or equal
// to it's frequency
if (x <= frequency)
{
// Delete extra occurrences
ans += (frequency - x);
}
// Delete every occurrence of x
else
ans += frequency;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 3, 2, 3, 4, 4, 4, 4, 5 };
int n = a.length;
System.out.println(MinDeletion(a, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the minimum # deletions required def MinDeletion(a, n) : # To store the frequency of # the array elements map = dict.fromkeys(a, 0); # Store frequency of each element for i in range(n) : map[a[i]] += 1; # To store the minimum deletions required ans = 0; for key,value in map.items() : # Value x = key; # It's frequency frequency = value; # If number less than or equal # to it's frequency if (x <= frequency) : # Delete extra occurrences ans += (frequency - x); # Delete every occurrence of x else : ans += frequency; return ans; # Driver code if __name__ == "__main__" : a = [ 2, 3, 2, 3, 4, 4, 4, 4, 5 ]; n = len(a); print(MinDeletion(a, n)); # This code is contributed by AnkitRai01
C#
// C# Implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the minimum
// deletions required
static int MinDeletion(int []a, int n)
{
// To store the frequency of
// the array elements
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Store frequency of each element
for (int i = 0 ; i < n; i++)
{
if(mp.ContainsKey(a[i]))
{
var val = mp[a[i]];
mp.Remove(a[i]);
mp.Add(a[i], val + 1);
}
else
{
mp.Add(a[i], 1);
}
}
// To store the minimum deletions required
int ans = 0;
foreach(KeyValuePair<int, int> i in mp)
{
// Value
int x = i.Key;
// It's frequency
int frequency = i.Value;
// If number less than or equal
// to it's frequency
if (x <= frequency)
{
// Delete extra occurrences
ans += (frequency - x);
}
// Delete every occurrence of x
else
ans += frequency;
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []a = { 2, 3, 2, 3, 4, 4, 4, 4, 5 };
int n = a.Length;
Console.WriteLine(MinDeletion(a, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javaScript implementation of the approach
// Function to return the minimum
// deletions required
function MinDeletion( a, n){
// To store the frequency of
// the array elements
let map = new Map();
// Store frequency of each element
for (let i = 0; i < n; i++){
if(map[a[i]])
map[a[i]]++;
else
map[a[i]] = 1
}
// To store the minimum deletions required
let ans = 0;
for(var m in map){
// Value
let x = m;
// It's frequency
let frequency = map[m];
// If number less than or equal
// to it's frequency
if (x <= frequency) {
// Delete extra occurrences
ans += (frequency - x);
}
// Delete every occurrence of x
else
ans += frequency;
};
return ans;
}
// Driver code
let a = [ 2, 3, 2, 3, 4, 4, 4, 4, 5 ];
let n = a.length;
document.write( MinDeletion(a, n));
// This code is contributed by rohitsingh07052.
</script>
Producción:
3
Complejidad de tiempo: O(n), donde n es el tamaño de la array dada.
Espacio auxiliar: O(n), donde n es el tamaño de la array dada.