Dado un arreglo arr[] de tamaño N que consta solo de los primeros M números naturales , la tarea es encontrar la longitud mínima del subarreglo que se requiere reemplazar de modo que la frecuencia de los elementos del arreglo sea N/M .
Nota: N es un múltiplo de M.
Ejemplos:
Entrada: M = 3, arr[] = {1, 1, 1, 1, 2, 3}
Salida: 2
Explicación:
Reemplazar el subarreglo sobre el rango [2, 3] con el elemento {2, 3} modifica el arreglo arr[] a {1, 1, 2, 3, 2, 3}. Ahora, la frecuencia de cada elemento del arreglo es N / M( = 6 / 3 = 2).
Por lo tanto, el subarreglo de longitud mínima que debe reemplazarse es 2.Entrada: M = 6, arr[] = {1, 3, 6, 6, 2, 1, 5, 4, 1, 4, 1, 2, 3, 2, 2, 2, 4, 3}
Salida: 4
Enfoque: el problema dado se puede resolver utilizando el enfoque de dos punteros para encontrar la longitud mínima del subarreglo que tiene todos los números fuera de este rango que son menores o iguales a N/M . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector , digamos mapu[] de tamaño M+1 con 0 para almacenar la frecuencia de cada elemento de la array.
- Inicialice la variable c como 0 para almacenar la cantidad de elementos que están presentes adicionalmente en la array.
- Itere sobre el rango [0, N] usando la variable i y realizando las siguientes tareas:
- Aumente el valor de arr[i] en el vector mapu[] en 1 .
- Si el valor de mapu[arr[i]] es igual a (N/M) + 1 , entonces aumente el valor de c en 1 .
- Si el valor de c es 0 , devuelva 0 como resultado.
- Inicialice la variable ans como N para almacenar la respuesta y los dos punteros L y R como 0 y (N – 1) para almacenar la izquierda y la derecha del rango.
- Iterar en un ciclo while hasta que R sea menor que N y realizar las siguientes tareas:
- Si el valor de (mapu[arr[R]] – 1) es igual a N/M , reste el valor de c por 1 .
- Si c es igual a 0 , itere en un ciclo while hasta que L sea menor que R y el valor de c sea igual a 0 y realice las siguientes tareas:
- Actualice el valor de ans como el mínimo de ans o (R – L + 1)
- Aumente el valor de mapu[arr[L]] en 1 y, si es mayor que N/M , aumente el valor de c en 1 .
- Aumente el valor de L en 1 .
- Aumente el valor de R en 1 .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum length
// of the subarray to be changed.
int minimumSubarray(vector<int> arr,
int n, int m)
{
// Stores the frequencies of array
// elements
vector<int> mapu(m + 1, 0);
// Stores the number of array elements
// that are present more than N/M times
int c = 0;
// Iterate over the range
for (int i = 0; i < n; i++) {
// Increment the frequency
mapu[arr[i]]++;
if (mapu[arr[i]] == (n / m) + 1)
c++;
}
// If the frequency of all array
// elements are already N/M
if (c == 0)
return 0;
// Stores the resultant length of
// the subarray
int ans = n;
// The left and right pointers
int l = 0, r = 0;
// Iterate over the range
while (r < n) {
// If the current element is
if (--mapu[arr[r]] == (n / m))
c--;
// If the value of c is 0, then
// find the possible answer
if (c == 0) {
// Iterate over the range
while (l <= r && c == 0) {
ans = min(ans, r - l + 1);
// If the element at left
// is making it extra
if (++mapu[arr[l]] > (n / m))
c++;
// Update the left pointer
l++;
}
}
// Update the right pointer
r++;
}
// Return the resultant length
return ans;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 1, 2, 1, 1, 2 };
int M = 2;
int N = arr.size();
cout << minimumSubarray(arr, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// Function to find the minimum length
// of the subarray to be changed.
public static int minimumSubarray(int[] arr, int n,
int m)
{
// Stores the frequencies of array
// elements
int[] mapu = new int[m + 1];
Arrays.fill(mapu, 0);
// Stores the number of array elements
// that are present more than N/M times
int c = 0;
// Iterate over the range
for(int i = 0; i < n; i++)
{
// Increment the frequency
mapu[arr[i]]++;
if (mapu[arr[i]] == (n / m) + 1)
c++;
}
// If the frequency of all array
// elements are already N/M
if (c == 0)
return 0;
// Stores the resultant length of
// the subarray
int ans = n;
// The left and right pointers
int l = 0, r = 0;
// Iterate over the range
while (r < n)
{
// If the current element is
if (--mapu[arr[r]] == (n / m))
c--;
// If the value of c is 0, then
// find the possible answer
if (c == 0)
{
// Iterate over the range
while (l <= r && c == 0)
{
ans = Math.min(ans, r - l + 1);
// If the element at left
// is making it extra
if (++mapu[arr[l]] > (n / m))
c++;
// Update the left pointer
l++;
}
}
// Update the right pointer
r++;
}
// Return the resultant length
return ans;
}
// Driver Code
public static void main(String args[])
{
int[] arr = { 1, 1, 2, 1, 1, 2 };
int M = 2;
int N = arr.length;
System.out.println(minimumSubarray(arr, N, M));
}
}
// This code is contributed by gfgking
Python3
# Python3 program for the above approach # Function to find the minimum length # of the subarray to be changed. def minimumSubarray(arr, n, m): # Stores the frequencies of array # elements mapu = [0 for i in range(m+1)] # Stores the number of array elements # that are present more than N/M times c = 0 # Iterate over the range for i in range(n): # Increment the frequency mapu[arr[i]] += 1 if (mapu[arr[i]] == (n // m) + 1): c += 1 # If the frequency of all array # elements are already N/M if (c == 0): return 0 # Stores the resultant length of # the subarray ans = n # The left and right pointers l = 0 r = 0 # Iterate over the range while (r < n): # If the current element is mapu[arr[r]] -= 1 if (mapu[arr[r]] == (n // m)): c -= 1 # If the value of c is 0, then # find the possible answer if (c == 0): # Iterate over the range while (l <= r and c == 0): ans = min(ans, r - l + 1) # If the element at left # is making it extra mapu[arr[l]] += 1 if (mapu[arr[l]] > (n // m)): c += 1 # Update the left pointer l += 1 # Update the right pointer r += 1 # Return the resultant length return ans # Driver Code if __name__ == '__main__': arr = [1, 1, 2, 1, 1, 2] M = 2 N = len(arr) print(minimumSubarray(arr, N, M)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum length
// of the subarray to be changed.
public static int minimumSubarray(int[] arr, int n,
int m)
{
// Stores the frequencies of array
// elements
int[] mapu = new int[m + 1];
Array.Fill(mapu, 0);
// Stores the number of array elements
// that are present more than N/M times
int c = 0;
// Iterate over the range
for(int i = 0; i < n; i++)
{
// Increment the frequency
mapu[arr[i]]++;
if (mapu[arr[i]] == (n / m) + 1)
c++;
}
// If the frequency of all array
// elements are already N/M
if (c == 0)
return 0;
// Stores the resultant length of
// the subarray
int ans = n;
// The left and right pointers
int l = 0, r = 0;
// Iterate over the range
while (r < n)
{
// If the current element is
if (--mapu[arr[r]] == (n / m))
c--;
// If the value of c is 0, then
// find the possible answer
if (c == 0)
{
// Iterate over the range
while (l <= r && c == 0)
{
ans = Math.Min(ans, r - l + 1);
// If the element at left
// is making it extra
if (++mapu[arr[l]] > (n / m))
c++;
// Update the left pointer
l++;
}
}
// Update the right pointer
r++;
}
// Return the resultant length
return ans;
}
// Driver Code
public static void Main(String []args)
{
int[] arr = { 1, 1, 2, 1, 1, 2 };
int M = 2;
int N = arr.Length;
Console.Write(minimumSubarray(arr, N, M));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum length
// of the subarray to be changed.
function minimumSubarray(arr, n, m)
{
// Stores the frequencies of array
// elements
let mapu = new Array(m + 1).fill(0);
// Stores the number of array elements
// that are present more than N/M times
let c = 0;
// Iterate over the range
for(let i = 0; i < n; i++)
{
// Increment the frequency
mapu[arr[i]]++;
if (mapu[arr[i]] == (n / m) + 1)
c++;
}
// If the frequency of all array
// elements are already N/M
if (c == 0)
return 0;
// Stores the resultant length of
// the subarray
let ans = n;
// The left and right pointers
let l = 0, r = 0;
// Iterate over the range
while (r < n)
{
// If the current element is
if (--mapu[arr[r]] == (n / m))
c--;
// If the value of c is 0, then
// find the possible answer
if (c == 0)
{
// Iterate over the range
while (l <= r && c == 0)
{
ans = Math.min(ans, r - l + 1);
// If the element at left
// is making it extra
if (++mapu[arr[l]] > (n / m))
c++;
// Update the left pointer
l++;
}
}
// Update the right pointer
r++;
}
// Return the resultant length
return ans;
}
// Driver Code
let arr = [ 1, 1, 2, 1, 1, 2 ];
let M = 2;
let N = arr.length;
document.write(minimumSubarray(arr, N, M));
// This code is contributed by Potta Lokesh
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por parthagarwal1962000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA