Dada una array de enteros arr[] de tamaño N , la tarea es encontrar la distancia mínima entre cualquier elemento más y menos frecuente de la array dada.
Ejemplos:
Entrada: arr[] = {1, 1, 2, 3, 2, 3, 3}
Salida: 1
Explicación: Los elementos menos frecuentes son 1 y 2, que se encuentran en los índices: 0, 1, 2, 4.
Considerando que, el el elemento más frecuente es 3 que ocurre en los índices: 3, 5, 6.
Entonces la distancia mínima es (3-2) = 1.Entrada: arr[] = {1, 3, 4, 4, 3, 4}
Salida: 2
Explicación: El elemento menos frecuente es 1 que ocurre en los índices: 0.
Mientras que el elemento más frecuente es 4 que ocurre en los índices: 2, 3, 5.
Entonces la distancia mínima es (2-0) = 2.
Enfoque : la idea es encontrar los índices de los elementos menos y más frecuentes en la array y encontrar la diferencia entre esos índices que es mínima. Siga los pasos a continuación para resolver el problema:
- Almacena la frecuencia de cada elemento en un HashMap .
- Almacene los elementos menos y más frecuentes en conjuntos separados .
- Traverse desde el inicio de la array. Si el elemento actual es el elemento menos frecuente, actualice el último índice del elemento menos frecuente.
- De lo contrario, si el elemento actual es el elemento más frecuente, calcule la distancia entre el índice actual y el último del elemento menos frecuente y actualice la distancia mínima requerida.
- De manera similar, recorra la array desde el final y repita los pasos 3 y 4 para encontrar la distancia mínima entre cualquier elemento más y menos frecuente de una array.
- Imprime la distancia mínima.
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 find the minimum
// distance between any two most
// and least frequent element
void getMinimumDistance(int a[], int n)
{
// Initialize sets to store the least
// and the most frequent elements
set<int> min_set;
set<int> max_set;
// Initialize variables to store
// max and min frequency
int max = 0, min = INT_MAX;
// Initialize HashMap to store
// frequency of each element
map<int, int> frequency;
// Loop through the array
for (int i = 0; i < n; i++) {
// Store the count of each element
frequency[a[i]] += 1;
}
// Store the least and most frequent
// elements in the respective sets
for (int i = 0; i < n; i++) {
// Store count of current element
int count = frequency[a[i]];
// If count is equal
// to max count
if (count == max) {
// Store in max set
max_set.insert(a[i]);
}
// If count is greater
// then max count
else if (count > max) {
// Empty max set
max_set.clear();
// Update max count
max = count;
// Store in max set
max_set.insert(a[i]);
}
// If count is equal
// to min count
if (count == min) {
// Store in min set
min_set.insert(a[i]);
}
// If count is less
// then max count
else if (count < min) {
// Empty min set
min_set.clear();
// Update min count
min = count;
// Store in min set
min_set.insert(a[i]);
}
}
// Initialize a variable to
// store the minimum distance
int min_dist = INT_MAX;
// Initialize a variable to
// store the last index of
// least frequent element
int last_min_found = -1;
// Traverse array
for (int i = 0; i < n; i++) {
// If least frequent element
if (min_set.find(a[i]) != min_set.end())
// Update last index of
// least frequent element
last_min_found = i;
// If most frequent element
if (max_set.find(a[i]) != max_set.end()
&& last_min_found != -1) {
// Update minimum distance
if ((i - last_min_found) < min_dist)
min_dist = i - last_min_found;
}
}
last_min_found = -1;
// Traverse array from the end
for (int i = n - 1; i >= 0; i--) {
// If least frequent element
if (min_set.find(a[i]) != min_set.end())
// Update last index of
// least frequent element
last_min_found = i;
// If most frequent element
if (max_set.find(a[i]) != max_set.end()
&& last_min_found != -1) {
// Update minimum distance
if ((last_min_found - i) > min_dist)
min_dist = last_min_found - i;
}
}
// Print the minimum distance
cout << (min_dist);
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 1, 2, 3, 2, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
getMinimumDistance(arr, N);
}
// This code is contributed by ukasp.
Java
// Java implementation of the approach
import java.util.*;
class GFG {
// Function to find the minimum
// distance between any two most
// and least frequent element
public static void
getMinimumDistance(int a[], int n)
{
// Initialize sets to store the least
// and the most frequent elements
Set<Integer> min_set = new HashSet<>();
Set<Integer> max_set = new HashSet<>();
// Initialize variables to store
// max and min frequency
int max = 0, min = Integer.MAX_VALUE;
// Initialize HashMap to store
// frequency of each element
HashMap<Integer, Integer> frequency
= new HashMap<>();
// Loop through the array
for (int i = 0; i < n; i++) {
// Store the count of each element
frequency.put(
a[i],
frequency
.getOrDefault(a[i], 0)
+ 1);
}
// Store the least and most frequent
// elements in the respective sets
for (int i = 0; i < n; i++) {
// Store count of current element
int count = frequency.get(a[i]);
// If count is equal
// to max count
if (count == max) {
// Store in max set
max_set.add(a[i]);
}
// If count is greater
// then max count
else if (count > max) {
// Empty max set
max_set.clear();
// Update max count
max = count;
// Store in max set
max_set.add(a[i]);
}
// If count is equal
// to min count
if (count == min) {
// Store in min set
min_set.add(a[i]);
}
// If count is less
// then max count
else if (count < min) {
// Empty min set
min_set.clear();
// Update min count
min = count;
// Store in min set
min_set.add(a[i]);
}
}
// Initialize a variable to
// store the minimum distance
int min_dist = Integer.MAX_VALUE;
// Initialize a variable to
// store the last index of
// least frequent element
int last_min_found = -1;
// Traverse array
for (int i = 0; i < n; i++) {
// If least frequent element
if (min_set.contains(a[i]))
// Update last index of
// least frequent element
last_min_found = i;
// If most frequent element
if (max_set.contains(a[i])
&& last_min_found != -1) {
// Update minimum distance
min_dist = Math.min(min_dist,
i - last_min_found);
}
}
last_min_found = -1;
// Traverse array from the end
for (int i = n - 1; i >= 0; i--) {
// If least frequent element
if (min_set.contains(a[i]))
// Update last index of
// least frequent element
last_min_found = i;
// If most frequent element
if (max_set.contains(a[i])
&& last_min_found != -1) {
// Update minimum distance
min_dist = Math.min(min_dist,
last_min_found - i);
}
}
// Print the minimum distance
System.out.println(min_dist);
}
// Driver Code
public static void
main(String[] args)
{
// Given array
int arr[] = { 1, 1, 2, 3, 2, 3, 3 };
int N = arr.length;
// Function Call
getMinimumDistance(arr, N);
}
}
Python3
# Python3 implementation of the approach
import sys
# Function to find the minimum
# distance between any two most
# and least frequent element
def getMinimumDistance(a, n):
# Initialize sets to store the least
# and the most frequent elements
min_set = {}
max_set = {}
# Initialize variables to store
# max and min frequency
max, min = 0, sys.maxsize + 1
# Initialize HashMap to store
# frequency of each element
frequency = {}
# Loop through the array
for i in range(n):
# Store the count of each element
frequency[a[i]] = frequency.get(a[i], 0) + 1
# Store the least and most frequent
# elements in the respective sets
for i in range(n):
# Store count of current element
count = frequency[a[i]]
# If count is equal
# to max count
if (count == max):
# Store in max set
max_set[a[i]] = 1
# If count is greater
# then max count
elif (count > max):
# Empty max set
max_set.clear()
# Update max count
max = count
# Store in max set
max_set[a[i]] = 1
# If count is equal
# to min count
if (count == min):
# Store in min set
min_set[a[i]] = 1
# If count is less
# then max count
elif (count < min):
# Empty min set
min_set.clear()
# Update min count
min = count
# Store in min set
min_set[a[i]] = 1
# Initialize a variable to
# store the minimum distance
min_dist = sys.maxsize + 1
# Initialize a variable to
# store the last index of
# least frequent element
last_min_found = -1
# Traverse array
for i in range(n):
# If least frequent element
if (a[i] in min_set):
# Update last index of
# least frequent element
last_min_found = i
# If most frequent element
if ((a[i] in max_set) and
last_min_found != -1):
# Update minimum distance
if i-last_min_found < min_dist:
min_dist = i - last_min_found
last_min_found = -1
# Traverse array from the end
for i in range(n - 1, -1, -1):
# If least frequent element
if (a[i] in min_set):
# Update last index of
# least frequent element
last_min_found = i;
# If most frequent element
if ((a[i] in max_set) and
last_min_found != -1):
# Update minimum distance
if min_dist > last_min_found - i:
min_dist = last_min_found - i
# Print the minimum distance
print(min_dist)
# Driver Code
if __name__ == '__main__':
# Given array
arr = [ 1, 1, 2, 3, 2, 3, 3 ]
N = len(arr)
# Function Call
getMinimumDistance(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the minimum
// distance between any two most
// and least frequent element
public static void
getMinimumDistance(int[] a, int n)
{
// Initialize sets to store the least
// and the most frequent elements
HashSet<int> min_set = new HashSet<int>();
HashSet<int> max_set = new HashSet<int>();
// Initialize variables to store
// max and min frequency
int max = 0, min = Int32.MaxValue;
// Initialize HashMap to store
// frequency of each element
Dictionary<int, int> frequency =
new Dictionary<int, int>();
// Loop through the array
for (int i = 0; i < n; i++) {
// Store the count of each element
if(!frequency.ContainsKey(a[i]))
frequency.Add(a[i],0);
frequency[a[i]]++;
}
// Store the least and most frequent
// elements in the respective sets
for (int i = 0; i < n; i++) {
// Store count of current element
int count = frequency[a[i]];
// If count is equal
// to max count
if (count == max) {
// Store in max set
max_set.Add(a[i]);
}
// If count is greater
// then max count
else if (count > max) {
// Empty max set
max_set.Clear();
// Update max count
max = count;
// Store in max set
max_set.Add(a[i]);
}
// If count is equal
// to min count
if (count == min) {
// Store in min set
min_set.Add(a[i]);
}
// If count is less
// then max count
else if (count < min) {
// Empty min set
min_set.Clear();
// Update min count
min = count;
// Store in min set
min_set.Add(a[i]);
}
}
// Initialize a variable to
// store the minimum distance
int min_dist = Int32.MaxValue;
// Initialize a variable to
// store the last index of
// least frequent element
int last_min_found = -1;
// Traverse array
for (int i = 0; i < n; i++) {
// If least frequent element
if (min_set.Contains(a[i]))
// Update last index of
// least frequent element
last_min_found = i;
// If most frequent element
if (max_set.Contains(a[i])
&& last_min_found != -1) {
// Update minimum distance
min_dist = Math.Min(min_dist,
i - last_min_found);
}
}
last_min_found = -1;
// Traverse array from the end
for (int i = n - 1; i >= 0; i--) {
// If least frequent element
if (min_set.Contains(a[i]))
// Update last index of
// least frequent element
last_min_found = i;
// If most frequent element
if (max_set.Contains(a[i])
&& last_min_found != -1) {
// Update minimum distance
min_dist = Math.Min(min_dist,
last_min_found - i);
}
}
// Print the minimum distance
Console.WriteLine(min_dist);
}
// Driver Code
static public void Main ()
{
// Given array
int[] arr = { 1, 1, 2, 3, 2, 3, 3 };
int N = arr.Length;
// Function Call
getMinimumDistance(arr, N);
}
}
// This code is contributed by patel2127.
Javascript
<script>
// Javascript implementation of the approach
// Function to find the minimum
// distance between any two most
// and least frequent element
function getMinimumDistance(a, n)
{
// Initialize sets to store the least
// and the most frequent elements
var min_set = new Set();
var max_set = new Set();
// Initialize variables to store
// max and min frequency
var max = 0, min = 1000000000;
// Initialize HashMap to store
// frequency of each element
var frequency = new Map();
// Loop through the array
for(var i = 0; i < n; i++)
{
// Store the count of each element
if(frequency.has(a[i]))
frequency.set(a[i],
frequency.get(a[i]) + 1)
else
frequency.set(a[i], 1)
}
// Store the least and most frequent
// elements in the respective sets
for(var i = 0; i < n; i++)
{
// Store count of current element
var count = frequency.get(a[i]);
// If count is equal
// to max count
if (count == max)
{
// Store in max set
max_set.add(a[i]);
}
// If count is greater
// then max count
else if (count > max)
{
// Empty max set
max_set = new Set();
// Update max count
max = count;
// Store in max set
max_set.add(a[i]);
}
// If count is equal
// to min count
if (count == min)
{
// Store in min set
min_set.add(a[i]);
}
// If count is less
// then max count
else if (count < min)
{
// Empty min set
min_set = new Set();
// Update min count
min = count;
// Store in min set
min_set.add(a[i]);
}
}
// Initialize a variable to
// store the minimum distance
var min_dist = 1000000000;
// Initialize a variable to
// store the last index of
// least frequent element
var last_min_found = -1;
// Traverse array
for(var i = 0; i < n; i++)
{
// If least frequent element
if (min_set.has(a[i]))
// Update last index of
// least frequent element
last_min_found = i;
// If most frequent element
if (max_set.has(a[i]) &&
last_min_found != -1)
{
// Update minimum distance
if ((i - last_min_found) < min_dist)
min_dist = i - last_min_found;
}
}
last_min_found = -1;
// Traverse array from the end
for(var i = n - 1; i >= 0; i--)
{
// If least frequent element
if (min_set.has(a[i]))
// Update last index of
// least frequent element
last_min_found = i;
// If most frequent element
if (max_set.has(a[i]) &&
last_min_found != -1)
{
// Update minimum distance
if ((last_min_found - i) > min_dist)
min_dist = last_min_found - i;
}
}
// Print the minimum distance
document.write(min_dist);
}
// Driver Code
// Given array
var arr = [ 1, 1, 2, 3, 2, 3, 3 ];
var N = arr.length;
// Function Call
getMinimumDistance(arr, N);
// This code is contributed by itsok
</script>
Producción:
1
Complejidad de tiempo: O(N), donde N es la longitud de la array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA