Dado un arreglo arr[] que contiene N elementos, la tarea es eliminar un subarreglo de longitud mínima posible del arreglo dado, de modo que todos los elementos restantes sean distintos por pares. Imprime la longitud mínima posible del subarreglo.
Ejemplos:
Entrada: N = 5, arr[] = {1, 2, 1, 2, 3}
Salida: 2
Explicación:
elimine la subarray {2, 1} para diferenciar los elementos.
Entrada: N = 5, arr[] = {1, 2, 3, 4, 5}
Salida: 0
Explicación:
Los elementos ya son distintos.
Enfoque ingenuo: el enfoque ingenuo para este problema es simplemente verificar todos los subarreglos posibles y encontrar la longitud del subarreglo más pequeño después de eliminarlo, todos los elementos en el arreglo se vuelven distintos por pares.
Complejidad temporal: O(N 3 )
Enfoque eficiente:
- Sea ans la longitud del subarreglo mínimo que, al eliminarse del arreglo dado, hace que los elementos del arreglo sean únicos.
- Podemos observar fácilmente que si todos los elementos del arreglo se vuelven distintos después de eliminar un subarreglo de longitud ans , entonces esta condición también se cumple para todos los valores mayores que ans .
- Esto significa que la solución para este problema es una función monótonamente creciente y podemos aplicar la búsqueda binaria en la respuesta.
- Ahora, para una longitud particular K de subarreglo, podemos verificar si los elementos de prefijo y sufijo de todos los subarreglos de longitud K son distintos por pares o no.
- Podemos hacer esto usando una técnica de ventana deslizante .
- Use un mapa hash para almacenar las frecuencias de los elementos en prefijo y sufijo, al mover la ventana hacia adelante, incremente la frecuencia del último elemento del prefijo y disminuya la frecuencia del primer elemento del sufijo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to make array elements
// pairwise distinct by removing at most
// one subarray of minimum length
#include <bits/stdc++.h>
using namespace std;
// Function to check if elements of
// Prefix and suffix of each sub array
// of size K are pairwise distinct or not
bool check(int a[], int n, int k)
{
// Hash map to store frequencies of
// elements of prefix and suffix
map<int, int> m;
// Variable to store number of
// occurrences of an element other
// than one
int extra = 0;
// Adding frequency of elements of suffix
// to hash for subarray starting from first
// index
// There is no prefix for this sub array
for (int i = k; i < n; i++)
m[a[i]]++;
// Counting extra elements in current Hash
// map
for (auto x : m)
extra += x.second - 1;
// If there are no extra elements return
// true
if (extra == 0)
return true;
// Check for remaining sub arrays
for (int i = 1; i + k - 1 < n; i++) {
// First element of suffix is now
// part of subarray which is being
// removed so, check for extra elements
if (m[a[i + k - 1]] > 1)
extra--;
// Decrement frequency of first
// element of the suffix
m[a[i + k - 1]]--;
// Increment frequency of last
// element of the prefix
m[a[i - 1]]++;
// Check for extra elements
if (m[a[i - 1]] > 1)
extra++;
// If there are no extra elements
// return true
if (extra == 0)
return true;
}
return false;
}
// Function for calculating minimum
// length of the subarray, which on
// removing make all elements pairwise
// distinct
int minlength(int a[], int n)
{
// Possible range of length of subarray
int lo = 0, hi = n + 1;
int ans = 0;
// Binary search to find minimum ans
while (lo < hi) {
int mid = (lo + hi) / 2;
if (check(a, n, mid)) {
ans = mid;
hi = mid;
}
else
lo = mid + 1;
}
return ans;
}
// Driver code
int main()
{
int a[5] = { 1, 2, 1, 2, 3 };
int n = sizeof(a) / sizeof(int);
cout << minlength(a, n);
}
Java
// Java program to make array elements
// pairwise distinct by removing at most
// one subarray of minimum length
import java.util.*;
import java.lang.*;
class GFG{
// Function to check if elements of
// Prefix and suffix of each sub array
// of size K are pairwise distinct or not
static boolean check(int a[], int n, int k)
{
// Hash map to store frequencies of
// elements of prefix and suffix
Map<Integer, Integer> m = new HashMap<>();
// Variable to store number of
// occurrences of an element other
// than one
int extra = 0;
// Adding frequency of elements of suffix
// to hash for subarray starting from first
// index
// There is no prefix for this sub array
for(int i = k; i < n; i++)
m.put(a[i], m.getOrDefault(a[i], 0) + 1);
// Counting extra elements in current Hash
// map
for(Integer x : m.values())
extra += x - 1;
// If there are no extra elements return
// true
if (extra == 0)
return true;
// Check for remaining sub arrays
for(int i = 1; i + k - 1 < n; i++)
{
// First element of suffix is now
// part of subarray which is being
// removed so, check for extra elements
if (m.get(a[i + k - 1]) > 1)
extra--;
// Decrement frequency of first
// element of the suffix
m.put(a[i + k - 1],
m.get(a[i + k - 1]) - 1);
// Increment frequency of last
// element of the prefix
m.put(a[i - 1], m.get(a[i - 1]) + 1);
// Check for extra elements
if (m.get(a[i - 1]) > 1)
extra++;
// If there are no extra elements
// return true
if (extra == 0)
return true;
}
return false;
}
// Function for calculating minimum
// length of the subarray, which on
// removing make all elements pairwise
// distinct
static int minlength(int a[], int n)
{
// Possible range of length of subarray
int lo = 0, hi = n + 1;
int ans = 0;
// Binary search to find minimum ans
while (lo < hi)
{
int mid = (lo + hi) / 2;
if (check(a, n, mid))
{
ans = mid;
hi = mid;
}
else
lo = mid + 1;
}
return ans;
}
// Driver Code
public static void main (String[] args)
{
int a[] = { 1, 2, 1, 2, 3 };
int n = a.length;
System.out.println(minlength(a, n));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to make array elements # pairwise distinct by removing at most # one subarray of minimum length from collections import defaultdict # Function to check if elements of # Prefix and suffix of each sub array # of size K are pairwise distinct or not def check(a, n, k): # Hash map to store frequencies of # elements of prefix and suffix m = defaultdict(int) # Variable to store number of # occurrences of an element other # than one extra = 0 # Adding frequency of elements of suffix # to hash for subarray starting from first # index # There is no prefix for this sub array for i in range(k, n): m[a[i]] += 1 # Counting extra elements in current Hash # map for x in m: extra += m[x] - 1 # If there are no extra elements return # true if (extra == 0): return True # Check for remaining sub arrays for i in range(1, i + k - 1 < n): # First element of suffix is now # part of subarray which is being # removed so, check for extra elements if (m[a[i + k - 1]] > 1): extra -= 1 # Decrement frequency of first # element of the suffix m[a[i + k - 1]] -= 1 # Increment frequency of last # element of the prefix m[a[i - 1]] += 1 # Check for extra elements if (m[a[i - 1]] > 1): extra += 1 # If there are no extra elements # return true if (extra == 0): return True return False # Function for calculating minimum # length of the subarray, which on # removing make all elements pairwise # distinct def minlength(a, n): # Possible range of length of subarray lo = 0 hi = n + 1 ans = 0 # Binary search to find minimum ans while (lo < hi): mid = (lo + hi) // 2 if (check(a, n, mid)): ans = mid hi = mid else: lo = mid + 1 return ans # Driver code if __name__ == "__main__": a = [ 1, 2, 1, 2, 3 ] n = len(a) print(minlength(a, n)) # This code is contributed by chitranayal
C#
// C# program to make array elements
// pairwise distinct by removing at most
// one subarray of minimum length
using System;
using System.Collections.Generic;
class GFG{
// Function to check if elements of
// Prefix and suffix of each sub array
// of size K are pairwise distinct or not
static bool check(int []a, int n, int k)
{
// Hash map to store frequencies of
// elements of prefix and suffix
Dictionary<int,
int> m = new Dictionary<int,
int>();
// Variable to store number of
// occurrences of an element other
// than one
int extra = 0;
// Adding frequency of elements of suffix
// to hash for subarray starting from first
// index
// There is no prefix for this sub array
for(int i = k; i < n; i++)
if(m.ContainsKey(a[i]))
m[a[i]] = m[a[i]] + 1;
else
m.Add(a[i], 1);
// Counting extra elements in current Hash
// map
foreach(int x in m.Keys)
extra += m[x] - 1;
// If there are no extra elements return
// true
if (extra == 0)
return true;
// Check for remaining sub arrays
for(int i = 1; i + k - 1 < n; i++)
{
// First element of suffix is now
// part of subarray which is being
// removed so, check for extra elements
if (m[a[i + k - 1]] > 1)
extra--;
// Decrement frequency of first
// element of the suffix
m[a[i + k - 1]] = m[a[i + k - 1]] - 1;
// Increment frequency of last
// element of the prefix
m[a[i - 1]] = m[a[i - 1]] + 1;
// Check for extra elements
if (m[a[i - 1]] > 1)
extra++;
// If there are no extra elements
// return true
if (extra == 0)
return true;
}
return false;
}
// Function for calculating minimum
// length of the subarray, which on
// removing make all elements pairwise
// distinct
static int minlength(int []a, int n)
{
// Possible range of length of subarray
int lo = 0, hi = n + 1;
int ans = 0;
// Binary search to find minimum ans
while (lo < hi)
{
int mid = (lo + hi) / 2;
if (check(a, n, mid))
{
ans = mid;
hi = mid;
}
else
lo = mid + 1;
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 1, 2, 1, 2, 3 };
int n = a.Length;
Console.WriteLine(minlength(a, n));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to make array elements
// pairwise distinct by removing at most
// one subarray of minimum length
// Function to check if elements of
// Prefix and suffix of each sub array
// of size K are pairwise distinct or not
function check(a, n, k)
{
// Hash map to store frequencies of
// elements of prefix and suffix
let m = new Map();
// Variable to store number of
// occurrences of an element other
// than one
let extra = 0;
// Adding frequency of elements of suffix
// to hash for subarray starting from first
// index
// There is no prefix for this sub array
for(let i = k; i < n; i++)
m.set(a[i], m.get(a[i])==null? 1 :m.get(a[i])+ 1);
// Counting extra elements in current Hash
// map
for(let x of m.values())
extra += x - 1;
// If there are no extra elements return
// true
if (extra == 0)
return true;
// Check for remaining sub arrays
for(let i = 1; i + k - 1 < n; i++)
{
// First element of suffix is now
// part of subarray which is being
// removed so, check for extra elements
if (m.get(a[i + k - 1]) > 1)
extra--;
// Decrement frequency of first
// element of the suffix
m.set(a[i + k - 1],
m.get(a[i + k - 1]) - 1);
// Increment frequency of last
// element of the prefix
m.set(a[i - 1], m.get(a[i - 1]) + 1);
// Check for extra elements
if (m.get(a[i - 1]) > 1)
extra++;
// If there are no extra elements
// return true
if (extra == 0)
return true;
}
return false;
}
// Function for calculating minimum
// length of the subarray, which on
// removing make all elements pairwise
// distinct
function minlength(a,n)
{
// Possible range of length of subarray
let lo = 0, hi = n + 1;
let ans = 0;
// Binary search to find minimum ans
while (lo < hi)
{
let mid = Math.floor((lo + hi) / 2);
if (check(a, n, mid))
{
ans = mid;
hi = mid;
}
else
lo = mid + 1;
}
return ans;
}
// Driver Code
let a = [1, 2, 1, 2, 3 ];
let n = a.length;
document.write(minlength(a, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad de tiempo: O(N * log(N)) , donde N es el tamaño de la array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ishayadav181 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA