Dada una array arr de tamaño N y un número K . La tarea es encontrar los elementos mínimos que se reemplazarán en la array con cualquier número tal que la array se componga de K elementos distintos.
Nota: la array puede consistir en elementos repetidos.
Ejemplos:
Entrada: arr[]={1, 2, 2, 8}, k = 1
Salida: 2
Los elementos a cambiar son 1, 8
Entrada: arr[]={1, 2, 7, 8, 2, 3, 2, 3}, k = 2
Salida: 3
Los elementos a cambiar son 1, 7, 8
Enfoque: dado que la tarea es reemplazar los elementos mínimos de la array, no reemplazaremos los elementos que tienen más frecuencia en la array. Entonces simplemente defina una array freq[] que almacene la frecuencia de cada número presente en la array arr , luego ordene freq en orden descendente. Por lo tanto, los primeros k elementos de la array de frecuencias no necesitan ser reemplazados.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to minimum changes required
// in an array for k distinct elements.
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
// Function to minimum changes required
// in an array for k distinct elements.
int Min_Replace(int arr[], int n, int k)
{
sort(arr, arr + n);
// Store the frequency of each element
int freq[MAX];
memset(freq, 0, sizeof freq);
int p = 0;
freq[p] = 1;
// Store the frequency of elements
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
++freq[p];
else
++freq[++p];
}
// Sort frequencies in descending order
sort(freq, freq + n, greater<int>());
// To store the required answer
int ans = 0;
for (int i = k; i <= p; i++)
ans += freq[i];
// Return the required answer
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 7, 8, 2, 3, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << Min_Replace(arr, n, k);
return 0;
}
Java
// C# program to minimum changes required
// in an array for k distinct elements.
import java.util.*;
class GFG
{
static int MAX = 100005;
// Function to minimum changes required
// in an array for k distinct elements.
static int Min_Replace(int [] arr,
int n, int k)
{
Arrays.sort(arr);
// Store the frequency of each element
Integer [] freq = new Integer[MAX];
Arrays.fill(freq, 0);
int p = 0;
freq[p] = 1;
// Store the frequency of elements
for (int i = 1; i < n; i++)
{
if (arr[i] == arr[i - 1])
++freq[p];
else
++freq[++p];
}
// Sort frequencies in descending order
Arrays.sort(freq, Collections.reverseOrder());
// To store the required answer
int ans = 0;
for (int i = k; i <= p; i++)
ans += freq[i];
// Return the required answer
return ans;
}
// Driver code
public static void main (String []args)
{
int [] arr = { 1, 2, 7, 8, 2, 3, 2, 3 };
int n = arr.length;
int k = 2;
System.out.println(Min_Replace(arr, n, k));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python 3 program to minimum changes required # in an array for k distinct elements. MAX = 100005 # Function to minimum changes required # in an array for k distinct elements. def Min_Replace(arr, n, k): arr.sort(reverse = False) # Store the frequency of each element freq = [0 for i in range(MAX)] p = 0 freq[p] = 1 # Store the frequency of elements for i in range(1, n, 1): if (arr[i] == arr[i - 1]): freq[p] += 1 else: p += 1 freq[p] += 1 # Sort frequencies in descending order freq.sort(reverse = True) # To store the required answer ans = 0 for i in range(k, p + 1, 1): ans += freq[i] # Return the required answer return ans # Driver code if __name__ == '__main__': arr = [1, 2, 7, 8, 2, 3, 2, 3] n = len(arr) k = 2 print(Min_Replace(arr, n, k)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to minimum changes required
// in an array for k distinct elements.
using System;
class GFG
{
static int MAX = 100005;
// Function to minimum changes required
// in an array for k distinct elements.
static int Min_Replace(int [] arr,
int n, int k)
{
Array.Sort(arr);
// Store the frequency of each element
int [] freq = new int[MAX];
int p = 0;
freq[p] = 1;
// Store the frequency of elements
for (int i = 1; i < n; i++)
{
if (arr[i] == arr[i - 1])
++freq[p];
else
++freq[++p];
}
// Sort frequencies in descending order
Array.Sort(freq);
Array.Reverse(freq);
// To store the required answer
int ans = 0;
for (int i = k; i <= p; i++)
ans += freq[i];
// Return the required answer
return ans;
}
// Driver code
public static void Main ()
{
int [] arr = { 1, 2, 7, 8, 2, 3, 2, 3 };
int n = arr.Length;
int k = 2;
Console.WriteLine(Min_Replace(arr, n, k));
}
}
// This code is contributed by ihritik
Javascript
<script>
// Javascript program to minimum changes required
// in an array for k distinct elements.
var MAX = 100005;
// Function to minimum changes required
// in an array for k distinct elements.
function Min_Replace(arr, n, k)
{
arr.sort((a,b)=>a-b)
// Store the frequency of each element
var freq = Array(MAX).fill(0);
var p = 0;
freq[p] = 1;
// Store the frequency of elements
for (var i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
++freq[p];
else
++freq[++p];
}
// Sort frequencies in descending order
freq.sort((a,b)=>b-a);
// To store the required answer
var ans = 0;
for (var i = k; i <= p; i++)
ans += freq[i];
// Return the required answer
return ans;
}
// Driver code
var arr = [1, 2, 7, 8, 2, 3, 2, 3];
var n = arr.length;
var k = 2;
document.write( Min_Replace(arr, n, k));
</script>
Producción:
3
Complejidad de tiempo: O (NlogN)
Publicación traducida automáticamente
Artículo escrito por ShivamKumarsingh1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA