Dado un arreglo arr[] que consiste en N enteros y un entero K , la tarea es encontrar la longitud del subarreglo más largo tal que cada elemento aparezca K veces.
Ejemplos:
Entrada: arr[] = {3, 5, 2, 2, 4, 6, 4, 6, 5}, K = 2
Salida: 8
Explicación: El subarreglo: {5, 2, 2, 4, 6, 4, 6, 5} de longitud 8 tiene la frecuencia de cada elemento como 2.Entrada: arr[] = {5, 5, 5, 5}, K = 3
Salida: 3
Explicación: El subarreglo: {5, 5, 5} de longitud 3 tiene la frecuencia de cada elemento como 3.
Enfoque: siga los pasos a continuación para resolver el problema:
- Genere todos los subarreglos posibles a partir del arreglo dado.
- Para cada subarreglo, inicialice dos mapas desordenados map1 y map2 , para almacenar la frecuencia de cada elemento y almacenar el conteo de elementos con las respectivas frecuencias.
- Si para cualquier subarreglo, el tamaño de map2 es igual a 1 y la frecuencia del elemento actual es K , eso significa que cada elemento aparece individualmente K veces en el subarreglo actual.
- Finalmente, devuelva el tamaño máximo de todos esos subarreglos.
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 length of
// required maximum subarray
int max_subarray_len(int arr[],
int N, int K)
{
// Initialize answer to 0
int ans = 0;
// Generate all subarrays having i as the
// starting index and j as the ending index
for (int i = 0; i < N; i++) {
// Stores frequency of subarray elements
unordered_map<int, int> map1;
// Stores subarray elements with
// respective frequencies
unordered_map<int, int> map2;
for (int j = i; j < N; j++) {
// Stores previous
// frequency of arr[j]
int prev_freq;
// If arr[j] hasn't
// occurred previously
if (map1.find(arr[j])
== map1.end()) {
// Set frequency as 0
prev_freq = 0;
}
else {
// Update previous frequency
prev_freq = map1[arr[j]];
}
// Increasing frequency
// of arr[j] by 1
map1[arr[j]]++;
// If frequency is stored
if (map2.find(prev_freq)
!= map2.end()) {
// If previous frequency is 1
if (map2[prev_freq] == 1) {
// Rove previous frequency
map2.erase(prev_freq);
}
else {
// Decrease previous frequency
map2[prev_freq]--;
}
}
int new_freq = prev_freq + 1;
// Increment new frequency
map2[new_freq]++;
// If updated frequency is equal to K
if (map2.size() == 1
&& (new_freq) == K) {
ans = max(
ans, j - i + 1);
}
}
}
// Return the maximum size
// of the subarray
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 3, 5, 2, 2, 4,
6, 4, 6, 5 };
int K = 2;
// Size of Array
int N = sizeof(arr)
/ sizeof(arr[0]);
// Function Call
cout << max_subarray_len(
arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the length of
// required maximum subarray
static int max_subarray_len(int arr[],
int N, int K)
{
// Initialize answer to 0
int ans = 0;
// Generate all subarrays having i as the
// starting index and j as the ending index
for (int i = 0; i < N; i++)
{
// Stores frequency of subarray elements
HashMap<Integer,Integer> map1 = new HashMap<>();
// Stores subarray elements with
// respective frequencies
HashMap<Integer,Integer> map2 = new HashMap<>();
for (int j = i; j < N; j++)
{
// Stores previous
// frequency of arr[j]
int prev_freq = 0;
// If arr[j] hasn't
// occurred previously
if (!map1.containsKey(arr[j]))
{
// Set frequency as 0
prev_freq = 0;
}
else
{
// Update previous frequency
prev_freq = map1.get(arr[j]);
}
// Increasing frequency
// of arr[j] by 1
if(map1.containsKey(arr[j]))
{
map1.put(arr[j], map1.get(arr[j]) + 1);
}
else
{
map1.put(arr[j], 1);
}
// If frequency is stored
if (map2.containsKey(prev_freq))
{
// If previous frequency is 1
if (map2.get(prev_freq) == 1)
{
// Rove previous frequency
map2.remove(prev_freq);
}
else
{
// Decrease previous frequency
map2.put(prev_freq, map2.get(prev_freq)-1);
}
}
int new_freq = prev_freq + 1;
// Increment new frequency
if(map2.containsKey(new_freq))
{
map2.put(new_freq, map2.get(new_freq) + 1);
}
else{
map2.put(new_freq, 1);
}
// If updated frequency is equal to K
if (map2.size() == 1
&& (new_freq) == K) {
ans = Math.max(
ans, j - i + 1);
}
}
}
// Return the maximum size
// of the subarray
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 3, 5, 2, 2, 4,
6, 4, 6, 5 };
int K = 2;
// Size of Array
int N = arr.length;
// Function Call
System.out.print(max_subarray_len(
arr, N, K));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above # approach from collections import defaultdict # Function to find the length of # required maximum subarray def max_subarray_len(arr, N, K): # Initialize answer to 0 ans = 0 # Generate all subarrays having # i as the starting index and j # as the ending index for i in range(N): # Stores frequency of subarray # elements map1 = defaultdict(int) # Stores subarray elements with # respective frequencies map2 = defaultdict(int) for j in range(i, N): # If arr[j] hasn't # occurred previously if (arr[j] not in map1): # Set frequency as 0 prev_freq = 0 else: # Update previous frequency prev_freq = map1[arr[j]] # Increasing frequency # of arr[j] by 1 map1[arr[j]] += 1 # If frequency is stored if prev_freq in map2: # If previous frequency is 1 if (map2[prev_freq] == 1): # Rove previous frequency del map2[prev_freq] else: # Decrease previous frequency map2[prev_freq] -= 1 new_freq = prev_freq + 1 # Increment new frequency map2[new_freq] += 1 # If updated frequency is equal # to K if (len(map2) == 1 and (new_freq) == K): ans = max(ans, j - i + 1) # Return the maximum size # of the subarray return ans # Driver Code if __name__ == "__main__": # Given array arr[] arr = [3, 5, 2, 2, 4, 6, 4, 6, 5] K = 2 # Size of Array N = len(arr) # Function Call print(max_subarray_len( arr, N, K)) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the length of
// required maximum subarray
static int max_subarray_len(int []arr,
int N, int K)
{
// Initialize answer to 0
int ans = 0;
// Generate all subarrays having i as the
// starting index and j as the ending index
for (int i = 0; i < N; i++)
{
// Stores frequency of subarray elements
Dictionary<int,int> map1 = new Dictionary<int,int>();
// Stores subarray elements with
// respective frequencies
Dictionary<int,int> map2 = new Dictionary<int,int>();
for (int j = i; j < N; j++)
{
// Stores previous
// frequency of arr[j]
int prev_freq = 0;
// If arr[j] hasn't
// occurred previously
if (!map1.ContainsKey(arr[j]))
{
// Set frequency as 0
prev_freq = 0;
}
else
{
// Update previous frequency
prev_freq = map1[arr[j]];
}
// Increasing frequency
// of arr[j] by 1
if(map1.ContainsKey(arr[j]))
{
map1[arr[j]] = map1[arr[j]] + 1;
}
else
{
map1.Add(arr[j], 1);
}
// If frequency is stored
if (map2.ContainsKey(prev_freq))
{
// If previous frequency is 1
if (map2[prev_freq] == 1)
{
// Rove previous frequency
map2.Remove(prev_freq);
}
else
{
// Decrease previous frequency
map2[prev_freq]= map2[prev_freq]-1;
}
}
int new_freq = prev_freq + 1;
// Increment new frequency
if(map2.ContainsKey(new_freq))
{
map2[new_freq] = map2[new_freq] + 1;
}
else{
map2.Add(new_freq, 1);
}
// If updated frequency is equal to K
if (map2.Count == 1
&& (new_freq) == K) {
ans = Math.Max(
ans, j - i + 1);
}
}
}
// Return the maximum size
// of the subarray
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 3, 5, 2, 2, 4,
6, 4, 6, 5 };
int K = 2;
// Size of Array
int N = arr.Length;
// Function Call
Console.Write(max_subarray_len(
arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to find the length of
// required maximum subarray
function max_subarray_len(arr,N,K)
{
// Initialize answer to 0
let ans = 0;
// Generate all subarrays having i as the
// starting index and j as the ending index
for (let i = 0; i < N; i++)
{
// Stores frequency of subarray elements
let map1 = new Map();
// Stores subarray elements with
// respective frequencies
let map2 = new Map();
for (let j = i; j < N; j++)
{
// Stores previous
// frequency of arr[j]
let prev_freq = 0;
// If arr[j] hasn't
// occurred previously
if (!map1.has(arr[j]))
{
// Set frequency as 0
prev_freq = 0;
}
else
{
// Update previous frequency
prev_freq = map1.get(arr[j]);
}
// Increasing frequency
// of arr[j] by 1
if(map1.has(arr[j]))
{
map1.set(arr[j], map1.get(arr[j]) + 1);
}
else
{
map1.set(arr[j], 1);
}
// If frequency is stored
if (map2.has(prev_freq))
{
// If previous frequency is 1
if (map2.get(prev_freq) == 1)
{
// Rove previous frequency
map2.delete(prev_freq);
}
else
{
// Decrease previous frequency
map2.set(prev_freq, map2.get(prev_freq)-1);
}
}
let new_freq = prev_freq + 1;
// Increment new frequency
if(map2.has(new_freq))
{
map2.set(new_freq, map2.get(new_freq) + 1);
}
else
{
map2.set(new_freq, 1);
}
// If updated frequency is equal to K
if (map2.size == 1
&& (new_freq) == K)
{
ans = Math.max(
ans, j - i + 1);
}
}
}
// Return the maximum size
// of the subarray
return ans;
}
// Driver Code
let arr=[ 3, 5, 2, 2, 4,
6, 4, 6, 5 ];
let K = 2;
// Size of Array
let N = arr.length;
// Function Call
document.write(max_subarray_len(
arr, N, K));
// This code is contributed by rag2127
</script>
Producción:
8
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por supratik_mitra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA