Dado un arreglo arr[] y un entero K , la tarea es dividir el arreglo en K grupos no vacíos donde cada grupo es un subarreglo del arreglo dado y cada elemento del arreglo es parte de un solo grupo. Todos los elementos de un grupo determinado deben tener el mismo valor. Puede realizar la siguiente operación cualquier número de veces:
Elija un elemento de la array y cambie su valor a cualquier valor. Imprime el número mínimo de tales operaciones requeridas para particionar la array.
Ejemplos:
Entrada: arr[] = {3, 1, 3, 3, 2, 1, 8, 5}, K = 3
Salida: 3
La array se puede dividir en {3, 3, 3, 3}, {2, 2 } y {8, 8}
cambiando el segundo elemento a 3, el sexto elemento
a 2 y el último elemento a 8.
Entrada: arr[] = {3, 3, 9, 10}, K = 3
Salida: 0
Divida la array en los grupos {3, 3}, {9} y {10}
sin realizar ninguna operación.
Observaciones:
- Si K = 1 , entonces el grupo es la array completa en sí. Para minimizar el número de operaciones necesarias, lo más intuitivo es cambiar todos los elementos de la array y hacerlos iguales a la moda de la array (elemento con la frecuencia más alta).
- Para los K grupos, el último elemento de la array siempre pertenecerá al K -ésimo grupo, mientras que el 1.er elemento pertenecerá al 1.er grupo .
- Si el K -ésimo grupo se ha encontrado correctamente, entonces el problema se reducirá a dividir la array restante en K-1 grupos usando operaciones mínimas.
Enfoque: Este problema se puede resolver mediante programación dinámica .
- Deje que DP(i, j) represente las operaciones mínimas necesarias para particionar el arreglo[1..i] en j grupos.
- Ahora, la tarea es encontrar DP(N, K), que son las operaciones mínimas necesarias para particionar el arreglo[1..N] en K grupos.
- Los casos base DP(i, j) donde j = 1 se pueden responder fácilmente. Dado que la array completa, la array [1..i] debe dividirse en un solo grupo. A partir de las observaciones, encuentra la moda del arreglo[1..i] y cambia todos los elementos en el arreglo[1..i] a la moda. Si el modo ocurrió x veces, entonces i – x elementos tendrán que cambiarse, es decir , i – x operaciones.
- Ya que, el K -ésimo grupo termina en el último elemento. Sin embargo, puede comenzar en varias posiciones posibles. Supongamos que el K -ésimo grupo comienza en algún índice , entonces la array[it..N] debe dividirse en un solo grupo y la array[1..(it – 1)] debe dividirse en K – 1 grupos. El costo de particionar el arreglo[1..(it – 1)] en K – 1 grupos es DP(it – 1, K – 1) y se puede calcular el costo de particionar el arreglo[it..N] en un solo grupo usando el modo y su observación de frecuencia.
- Para encontrar la frecuencia del elemento que aparece más en un rango [it..i] , podemos usar un mapa hash y una variable entera. La variable entera representa la frecuencia más alta actual. El mapa almacena todos los elementos vistos hasta ahora junto con sus frecuencias. Cada vez que se ve un elemento, su frecuencia se incrementa en el mapa, si ahora la frecuencia de este elemento es más alta que la frecuencia más alta actual, actualizamos la frecuencia más alta actual a la frecuencia del elemento recién visto. Consulte esto para el enfoque.
- Por lo tanto , DP(i, j) es el mínimo de DP(it – 1, j – 1) + costo de dividir el arreglo[it..i] en 1 grupo para todos los valores posibles de it .
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 number
// of operations needed to partition
// the array in k contiguous groups
// such that all elements of a
// given group are identical
int getMinimumOps(vector<int> ar, int k)
{
// n is the size of the array
int n = ar.size();
// dp(i, j) represents the minimum cost for
// partitioning the array[0..i] into j groups
int dp[n][k + 1];
// Base case, cost is 0 for parititoning the
// array[0..0] into 1 group
dp[0][1] = 0;
// Fill dp(i, j) and the answer will
// be stored at dp(n-1, k)
for (int i = 1; i < n; i++) {
// The maximum groups that the segment 0..i can
// be divided in is represented by maxGroups
int maxGroups = min(k, i + 1);
for (int j = 1; j <= maxGroups; j++) {
// Initialize dp(i, j) to infinity
dp[i][j] = INT_MAX;
// Divide segment 0..i in 1 group
if (j == 1) {
// map and freqOfMode are together used to
// keep track of the frequency of the most
// occurring element in [0..i]
unordered_map<int, int> freq;
int freqOfMode = 0;
for (int it = 0; it <= i; it++) {
freq[ar[it]]++;
int newElementFreq = freq[ar[it]];
if (newElementFreq > freqOfMode)
freqOfMode = newElementFreq;
}
// Change all the elements in the range
// 0..i to the most frequent element
// in this range
dp[i][1] = (i + 1) - freqOfMode;
}
else {
unordered_map<int, int> freq;
int freqOfMode = 0;
// If the jth group is the segment from
// it..i, we change all the elements in this
// range to this range's most occurring element
for (int it = i; it >= j - 1; it--) {
freq[ar[it]]++;
int newElementFreq = freq[ar[it]];
if (newElementFreq > freqOfMode)
freqOfMode = newElementFreq;
// Number of elements we need to change
// in the jth group i.e. the range it..i
int elementsToChange = i - it + 1;
elementsToChange -= freqOfMode;
// For all the possible sizes of the jth
// group that end at the ith element
// we pick the size that gives us the minimum
// cost for dp(i, j)
// elementsToChange is the cost of making
// all the elements in the jth group identical
// and we make use of dp(it - 1, j - 1) to
// find the overall minimal cost
dp[i][j] = min(dp[it - 1][j - 1]
+ elementsToChange,
dp[i][j]);
}
}
}
}
// Return the minimum cost for
// partitioning array[0..n-1]
// into k groups which is
// stored at dp(n-1, k)
return dp[n - 1][k];
}
// Driver code
int main()
{
int k = 3;
vector<int> ar = { 3, 1, 3, 3, 2, 1, 8, 5 };
cout << getMinimumOps(ar, k);
return 0;
}
Java
// Java implementation of above approach
class GFG
{
// Function to return the minimum number
// of operations needed to partition
// the array in k contiguous groups
// such that all elements of a
// given group are identical
static int getMinimumOps(int ar[], int k)
{
// n is the size of the array
int n = ar.length;
// dp(i, j) represents the minimum cost for
// partitioning the array[0..i] into j groups
int dp[][] = new int[n][k + 1];
// Base case, cost is 0 for parititoning the
// array[0..0] into 1 group
dp[0][1] = 0;
// Fill dp(i, j) and the answer will
// be stored at dp(n-1, k)
for (int i = 1; i < n; i++)
{
// The maximum groups that the segment 0..i can
// be divided in is represented by maxGroups
int maxGroups = Math.min(k, i + 1);
for (int j = 1; j <= maxGroups; j++)
{
// Initialize dp(i, j) to infinity
dp[i][j] = Integer.MAX_VALUE;
// Divide segment 0..i in 1 group
if (j == 1)
{
// map and freqOfMode are together used to
// keep track of the frequency of the most
// occurring element in [0..i]
int freq[] = new int[100000];
int freqOfMode = 0;
for (int it = 0; it <= i; it++)
{
freq[ar[it]]++;
int newElementFreq = freq[ar[it]];
if (newElementFreq > freqOfMode)
freqOfMode = newElementFreq;
}
// Change all the elements in the range
// 0..i to the most frequent element
// in this range
dp[i][1] = (i + 1) - freqOfMode;
}
else
{
int freq[] = new int[100000];
int freqOfMode = 0;
// If the jth group is the segment from
// it..i, we change all the elements in this
// range to this range's most occurring element
for (int it = i; it >= j - 1; it--)
{
freq[ar[it]]++;
int newElementFreq = freq[ar[it]];
if (newElementFreq > freqOfMode)
freqOfMode = newElementFreq;
// Number of elements we need to change
// in the jth group i.e. the range it..i
int elementsToChange = i - it + 1;
elementsToChange -= freqOfMode;
// For all the possible sizes of the jth
// group that end at the ith element
// we pick the size that gives us the minimum
// cost for dp(i, j)
// elementsToChange is the cost of making
// all the elements in the jth group identical
// and we make use of dp(it - 1, j - 1) to
// find the overall minimal cost
dp[i][j] = Math.min(dp[it - 1][j - 1] +
elementsToChange, dp[i][j]);
}
}
}
}
// Return the minimum cost for
// partitioning array[0..n-1]
// into k groups which is
// stored at dp(n-1, k)
return dp[n - 1][k];
}
// Driver code
public static void main(String args[])
{
int k = 3;
int ar[] = { 3, 1, 3, 3, 2, 1, 8, 5 };
System.out.println(getMinimumOps(ar, k));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Function to return the minimum number # of operations needed to partition # the array in k contiguous groups # such that all elements of a # given group are identical def getMinimumOps(ar, k): # n is the size of the array n = len(ar) # dp(i, j) represents the minimum cost for # partitioning the array[0..i] into j groups dp = [[ 0 for i in range(k + 1)] for i in range(n)] # Base case, cost is 0 for parititoning the # array[0..0] into 1 group dp[0][1] = 0 # Fill dp(i, j) and the answer will # be stored at dp(n-1, k) for i in range(1, n): # The maximum groups that the segment 0..i can # be divided in is represented by maxGroups maxGroups = min(k, i + 1) for j in range(1, maxGroups + 1): # Initialize dp(i, j) to infinity dp[i][j] = 10**9 # Divide segment 0..i in 1 group if (j == 1): # map and freqOfMode are together used to # keep track of the frequency of the most # occurring element in [0..i] freq1 = dict() freqOfMode = 0 for it in range(0, i + 1): freq1[ar[it]] = freq1.get(ar[it], 0) + 1 newElementFreq = freq1[ar[it]] if (newElementFreq > freqOfMode): freqOfMode = newElementFreq # Change all the elements in the range # 0..i to the most frequent element # in this range dp[i][1] = (i + 1) - freqOfMode else: freq = dict() freqOfMode = 0 # If the jth group is the segment from # it..i, we change all the elements in this # range to this range's most occurring element for it in range(i, j - 2, -1): #print(i,j,it) freq[ar[it]] = freq.get(ar[it], 0) + 1 newElementFreq = freq[ar[it]] if (newElementFreq > freqOfMode): freqOfMode = newElementFreq # Number of elements we need to change # in the jth group i.e. the range it..i elementsToChange = i - it + 1 elementsToChange -= freqOfMode # For all the possible sizes of the jth # group that end at the ith element # we pick the size that gives us the minimum # cost for dp(i, j) # elementsToChange is the cost of making # all the elements in the jth group identical # and we make use of dp(it - 1, j - 1) to # find the overall minimal cost dp[i][j] = min(dp[it - 1][j - 1] + elementsToChange, dp[i][j]) # Return the minimum cost for # partitioning array[0..n-1] # into k groups which is # stored at dp(n-1, k) return dp[n - 1][k] # Driver code k = 3 ar =[3, 1, 3, 3, 2, 1, 8, 5] print(getMinimumOps(ar, k)) # This code is contributed by Mohit Kumar
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to return the minimum number
// of operations needed to partition
// the array in k contiguous groups
// such that all elements of a
// given group are identical
static int getMinimumOps(int []ar, int k)
{
// n is the size of the array
int n = ar.Length;
// dp(i, j) represents the minimum cost for
// partitioning the array[0..i] into j groups
int [,]dp = new int[n, k + 1];
// Base case, cost is 0 for parititoning the
// array[0..0] into 1 group
dp[0, 1] = 0;
// Fill dp(i, j) and the answer will
// be stored at dp(n-1, k)
for (int i = 1; i < n; i++)
{
// The maximum groups that the segment 0..i can
// be divided in is represented by maxGroups
int maxGroups = Math.Min(k, i + 1);
for (int j = 1; j <= maxGroups; j++)
{
// Initialize dp(i, j) to infinity
dp[i, j] = int.MaxValue;
// Divide segment 0..i in 1 group
if (j == 1)
{
// map and freqOfMode are together used to
// keep track of the frequency of the most
// occurring element in [0..i]
int []freq = new int[100000];
int freqOfMode = 0;
for (int it = 0; it <= i; it++)
{
freq[ar[it]]++;
int newElementFreq = freq[ar[it]];
if (newElementFreq > freqOfMode)
freqOfMode = newElementFreq;
}
// Change all the elements in the range
// 0..i to the most frequent element
// in this range
dp[i, 1] = (i + 1) - freqOfMode;
}
else
{
int []freq = new int[100000];
int freqOfMode = 0;
// If the jth group is the segment from
// it..i, we change all the elements in this
// range to this range's most occurring element
for (int it = i; it >= j - 1; it--)
{
freq[ar[it]]++;
int newElementFreq = freq[ar[it]];
if (newElementFreq > freqOfMode)
freqOfMode = newElementFreq;
// Number of elements we need to change
// in the jth group i.e. the range it..i
int elementsToChange = i - it + 1;
elementsToChange -= freqOfMode;
// For all the possible sizes of the jth
// group that end at the ith element
// we pick the size that gives us the minimum
// cost for dp(i, j)
// elementsToChange is the cost of making
// all the elements in the jth group identical
// and we make use of dp(it - 1, j - 1) to
// find the overall minimal cost
dp[i, j] = Math.Min(dp[it - 1, j - 1] +
elementsToChange, dp[i, j]);
}
}
}
}
// Return the minimum cost for
// partitioning array[0..n-1]
// into k groups which is
// stored at dp(n-1, k)
return dp[n - 1, k];
}
// Driver code
public static void Main(String []args)
{
int k = 3;
int []ar = {3, 1, 3, 3, 2, 1, 8, 5};
Console.WriteLine(getMinimumOps(ar, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of above approach
// Function to return the minimum number
// of operations needed to partition
// the array in k contiguous groups
// such that all elements of a
// given group are identical
function getMinimumOps(ar, k)
{
// n is the size of the array
let n = ar.length;
// dp(i, j) represents the minimum cost for
// partitioning the array[0..i] into j groups
let dp = new Array(n);
for(let i = 0; i < dp.length; i++)
{
dp[i] = new Array(k+1);
for(let j = 0; j < (k + 1); j++)
{
dp[i][j] = 0;
}
}
// Base case, cost is 0 for parititoning the
// array[0..0] into 1 group
dp[0][1] = 0;
// Fill dp(i, j) and the answer will
// be stored at dp(n-1, k)
for (let i = 1; i < n; i++)
{
// The maximum groups that the segment 0..i can
// be divided in is represented by maxGroups
let maxGroups = Math.min(k, i + 1);
for (let j = 1; j <= maxGroups; j++)
{
// Initialize dp(i, j) to infinity
dp[i][j] = Number.MAX_VALUE;
// Divide segment 0..i in 1 group
if (j == 1)
{
// map and freqOfMode are together used to
// keep track of the frequency of the most
// occurring element in [0..i]
let freq = new Array(100000);
for(let i=0;i<freq.length;i++)
{
freq[i]=0;
}
let freqOfMode = 0;
for (let it = 0; it <= i; it++)
{
freq[ar[it]]++;
let newElementFreq = freq[ar[it]];
if (newElementFreq > freqOfMode)
freqOfMode = newElementFreq;
}
// Change all the elements in the range
// 0..i to the most frequent element
// in this range
dp[i][1] = (i + 1) - freqOfMode;
}
else
{
let freq = new Array(100000);
for(let i = 0; i < freq.length; i++)
{
freq[i] = 0;
}
let freqOfMode = 0;
// If the jth group is the segment from
// it..i, we change all the elements in this
// range to this range's most occurring element
for (let it = i; it >= j - 1; it--)
{
freq[ar[it]]++;
let newElementFreq = freq[ar[it]];
if (newElementFreq > freqOfMode)
freqOfMode = newElementFreq;
// Number of elements we need to change
// in the jth group i.e. the range it..i
let elementsToChange = i - it + 1;
elementsToChange -= freqOfMode;
// For all the possible sizes of the jth
// group that end at the ith element
// we pick the size that gives us the minimum
// cost for dp(i, j)
// elementsToChange is the cost of making
// all the elements in the jth group identical
// and we make use of dp(it - 1, j - 1) to
// find the overall minimal cost
dp[i][j] = Math.min(dp[it - 1][j - 1] +
elementsToChange, dp[i][j]);
}
}
}
}
// Return the minimum cost for
// partitioning array[0..n-1]
// into k groups which is
// stored at dp(n-1, k)
return dp[n - 1][k];
}
// Driver code
let k = 3;
let ar=[3, 1, 3, 3, 2, 1, 8, 5 ];
document.write(getMinimumOps(ar, k));
// This code is contributed by unknown2108
</script>
Producción:
3
Complejidad de tiempo: O (N * N * K) donde N es el tamaño de la array y K es la cantidad de grupos en los que se debe dividir la array.
Complejidad espacial: O(N * K)
Publicación traducida automáticamente
Artículo escrito por KartikArora y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA