Dada una array de enteros arr[] . Cree una nueva array que sea una rotación de la array dada y encuentre la distancia máxima de Hamming entre ambas arrays.
La distancia de Hamming entre dos arrays o strings de igual longitud es el número de posiciones en las que los caracteres (elementos) correspondientes son diferentes .
Nota: Puede haber más de una salida para la entrada dada.
Ejemplo:
Entrada: arr[] = [1, 4, 1]
Salida: 2
Explicación: Distancia máxima de hamming = 2, esta distancia de hamming con 4 1 1 o 1 1 4
Entrada: arr[] = [2, 4, 8, 0]
Salida: 4
Explicación: Distancia máxima de hamming = 4, esta distancia de hamming con 4 8 0 2. Todos los lugares pueden ser ocupados por otro dígito. Otras soluciones pueden ser 8 0 2 4, 4 0 2 8 etc.
Enfoque: este problema se puede resolver de manera eficiente utilizando Hashmap . Siga los pasos que se indican a continuación para resolver el problema.
- Itere a través de la array arr[] y almacene los valores de la array en un HashMap <key, value> . El valor puede ser Lista<> o string según el interés.
- Agregue el valor en hashmap, hashMap.add(arrvalue, list).
- Compruebe esta condición:
- Cuando hashMap.contains(arrValue) entonces hashmap.get(arrayValue).append(index).
- Verifique el tamaño del hashmap, si el tamaño == 1 , entonces
- distancia máxima de hamming = 0 . Porque todos los valores son iguales.
- Ejecute for each loop, for each key si el tamaño de la lista = 1 entonces
- distancia máxima de hamming = n . Porque todos los valores son diferentes.
- Cree una array de tamaño: 1 de la array dada para almacenar las ocurrencias similares que pueden ocurrir.
- Después de almacenar todos los índices de la array, almacene los valores en hashMap .
- Para cada diferencia encontrada un += 1 . Esta diferencia dice el número de rotaciones que se necesitarían para tener el mismo valor en la misma posición.
- Encuentre el valor mínimo en la array y obtenga el índice => valores mínimos iguales => distancia máxima de hamming.
A continuación se muestra la implementación del enfoque anterior:
C++
// Find a rotation with maximum hamming distance
#include<bits/stdc++.h>
using namespace std;
// Function to return the min value
int getMinValue(vector<int> numbers)
{
// var to stor the min value
int minValue = numbers[0];
for(int i = 1; i < numbers.size(); i++)
{
// Condition to check if value is
// lesser from the minValue or not
if (numbers[i] < minValue)
{
minValue = numbers[i];
}
}
// Return the minValue
return minValue;
}
// Function to get the hamming distance
int maxHammingDistance(vector<int> array)
{
int n = array.size();
vector<int> repetitionsOnRotations(n - 1,0);
// Create the map to store the key value pair
map<int, vector<int>> indexesOfElements;
for(int i = 0; i < n; i++)
{
int key = array[i];
// Take empty list of integers
// to store the integer
vector<int>indexes;
if (indexesOfElements.find(key) !=
indexesOfElements.end())
{
indexes = indexesOfElements[key];
}
else
{
indexes.clear();
}
// Add the value in list index
indexes.push_back(i);
indexesOfElements[key] = indexes;
}
// Run the for loop and get the
// value from hash map one at a time
for(auto x : indexesOfElements)
{
vector<int> indexes = x.second;
for(int i = 0; i < indexes.size() - 1; i++)
{
for(int j = i + 1; j < indexes.size(); j++)
{
// Store the diff into the variable
int diff = indexes[i] - indexes[j];
// Check the condition if diff
// is less then zero or not
if (diff < 0)
{
repetitionsOnRotations[-diff - 1] += 1;
diff = n + diff;
}
repetitionsOnRotations += 1;
}
}
}
// Return the hamming distance
return n - getMinValue(repetitionsOnRotations);
}
// Driver code
int main()
{
// Example 1
vector<int> array{ 1, 4, 1 };
int result1 = maxHammingDistance(array);
cout << result1 << endl;
// Example 2
vector<int> array2{ 2, 4, 8, 0 };
int result2 = maxHammingDistance(array2);
cout << result2 << endl;
}
// This code is contributed by ipg2016107
Java
// Find a rotation with maximum hamming distance
import java.io.*;
import java.util.*;
class GFG {
// Function to return the min value
public static int getMinValue(int[] numbers)
{
// var to stor the min value
int minValue = numbers[0];
for (int i = 1; i < numbers.length; i++) {
// Condition to check if value is
// lesser from the minValue or not
if (numbers[i] < minValue) {
minValue = numbers[i];
}
}
// Return the minValue
return minValue;
}
// Function to get the hamming distance
public static int maxHammingDistance(int[] array)
{
int n = array.length;
int[] repetitionsOnRotations = new int[n - 1];
// Create the map to store the key value pair
Map<Integer, List<Integer> > indexesOfElements
= new HashMap<>();
for (int i = 0; i < n; i++) {
int key = array[i];
// Take empty list of integers
// to store the integer
List<Integer> indexes = null;
if (indexesOfElements.containsKey(key)) {
indexes = indexesOfElements.get(key);
}
else {
indexes = new ArrayList<>();
}
// Add the value in list index
indexes.add(i);
indexesOfElements.put(key, indexes);
}
// Run the for loop and get the
// value from hash map one at a time
for (Map.Entry<Integer, List<Integer> > keys :
indexesOfElements.entrySet()) {
List<Integer> indexes = keys.getValue();
for (int i = 0; i < indexes.size() - 1; i++) {
for (int j = i + 1; j < indexes.size(); j++) {
// Store the diff into the variable
int diff
= indexes.get(i) - indexes.get(j);
// Check the condition if diff
// is less then zero or not
if (diff < 0) {
repetitionsOnRotations[(-diff) - 1] += 1;
diff = n + diff;
}
repetitionsOnRotations += 1;
}
}
}
// Return the hamming distance
return n - (getMinValue(repetitionsOnRotations));
}
// Driver code
public static void main(String[] args)
{
// Example 1
int[] array = { 1, 4, 1 };
int result1 = GFG.maxHammingDistance(array);
System.out.println(result1);
// Example 2
int[] array2 = { 2, 4, 8, 0 };
int result2 = GFG.maxHammingDistance(array2);
System.out.println(result2);
}
}
Python3
# Find a rotation with maximum hamming distance
# Function to return the min value
def getMinValue(numbers):
# var to stor the min value
minValue = numbers[0]
for i in range(1, len(numbers)):
# Condition to check if value is
# lesser from the minValue or not
if (numbers[i] < minValue):
minValue = numbers[i]
# Return the minValue
return minValue
# Function to get the hamming distance
def maxHammingDistance(array):
n = len(array)
repetitionsOnRotations = [0] * (n - 1)
# Create the map to store the key value pair
indexesOfElements = {}
for i in range(n):
key = array[i]
# Take empty list of integers
# to store the integer
indexes = []
if (key in indexesOfElements):
indexes = indexesOfElements[key]
else:
indexes = []
# Add the value in list index
indexes.append(i)
indexesOfElements[key] = indexes
# Run the for loop and get the
# value from hash map one at a time
for indexes in indexesOfElements.values():
for i in range(len(indexes) - 1):
for j in range(i + 1, len(indexes)):
# Store the diff into the variable
diff = indexes[i] - indexes[j]
# Check the condition if diff
# is less then zero or not
if (diff < 0):
repetitionsOnRotations[-diff - 1] += 1
diff = n + diff
repetitionsOnRotations += 1
# Return the hamming distance
return n - getMinValue(repetitionsOnRotations)
# Driver code
# Example 1
array = [1, 4, 1]
result1 = maxHammingDistance(array)
print(result1)
# Example 2
array2 = [2, 4, 8, 0]
result2 = maxHammingDistance(array2)
print(result2)
# This code is contributed by _saurabh_jaiswal
C#
// Find a rotation with maximum hamming distance
using System;
using System.Collections.Generic;
class GFG{
// Function to return the min value
public static int getMinValue(int[] numbers)
{
// var to stor the min value
int minValue = numbers[0];
for(int i = 1; i < numbers.Length; i++)
{
// Condition to check if value is
// lesser from the minValue or not
if (numbers[i] < minValue)
{
minValue = numbers[i];
}
}
// Return the minValue
return minValue;
}
// Function to get the hamming distance
public static int maxHammingDistance(int[] array)
{
int n = array.Length;
int[] repetitionsOnRotations = new int[n - 1];
// Create the map to store the key value pair
Dictionary<int,
List<int>> indexesOfElements = new Dictionary<int,
List<int>>();
for(int i = 0; i < n; i++)
{
int key = array[i];
// Take empty list of integers
// to store the integer
List<int> indexes = null;
if (indexesOfElements.ContainsKey(key))
{
indexes = indexesOfElements[key];
}
else
{
indexes = new List<int>();
}
// Add the value in list index
indexes.Add(i);
if (!indexesOfElements.ContainsKey(key))
indexesOfElements.Add(key, indexes);
}
// Run the for loop and get the
// value from hash map one at a time
foreach(KeyValuePair<int,
List<int>> keys in indexesOfElements)
{
List<int> indexes = keys.Value;
for(int i = 0; i < indexes.Count - 1; i++)
{
for(int j = i + 1; j < indexes.Count; j++)
{
// Store the diff into the variable
int diff = indexes[i] - indexes[j];
// Check the condition if diff
// is less then zero or not
if (diff < 0)
{
repetitionsOnRotations[(-diff) - 1] += 1;
diff = n + diff;
}
repetitionsOnRotations += 1;
}
}
}
// Return the hamming distance
return n - (getMinValue(repetitionsOnRotations));
}
// Driver code
public static void Main(String[] args)
{
// Example 1
int[] array = { 1, 4, 1 };
int result1 = GFG.maxHammingDistance(array);
Console.WriteLine(result1);
// Example 2
int[] array2 = { 2, 4, 8, 0 };
int result2 = GFG.maxHammingDistance(array2);
Console.WriteLine(result2);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// Find a rotation with maximum hamming distance
// Function to return the min value
function getMinValue(numbers)
{
// var to stor the min value
let minValue = numbers[0];
for(let i = 1; i < numbers.length; i++)
{
// Condition to check if value is
// lesser from the minValue or not
if (numbers[i] < minValue)
{
minValue = numbers[i];
}
}
// Return the minValue
return minValue;
}
// Function to get the hamming distance
function maxHammingDistance(array)
{
let n = array.length;
let repetitionsOnRotations = new Array(n - 1).fill(0);
// Create the map to store the key value pair
let indexesOfElements = new Map();
for(let i = 0; i < n; i++)
{
let key = array[i];
// Take empty list of integers
// to store the integer
let indexes = [];
if (indexesOfElements.has(key))
{
indexes = indexesOfElements.get(key);
}
else
{
indexes = [];
}
// Add the value in list index
indexes.push(i);
indexesOfElements.set(key, indexes);
}
// Run the for loop and get the
// value from hash map one at a time
for(let keys of indexesOfElements)
{
let indexes = keys[1];
for(let i = 0; i < indexes.length - 1; i++)
{
for(let j = i + 1; j < indexes.length; j++)
{
// Store the diff into the variable
let diff = indexes[i] - indexes[j];
// Check the condition if diff
// is less then zero or not
if (diff < 0)
{
repetitionsOnRotations[-diff - 1] += 1;
diff = n + diff;
}
repetitionsOnRotations += 1;
}
}
}
// Return the hamming distance
return n - getMinValue(repetitionsOnRotations);
}
// Driver code
// Example 1
let array = [ 1, 4, 1 ];
let result1 = maxHammingDistance(array);
document.write(result1 + "<br>");
// Example 2
let array2 = [ 2, 4, 8, 0 ];
let result2 = maxHammingDistance(array2);
document.write(result2);
// This code is contributed by gfgking
</script>
Producción:
2 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por SaiDeepaBhavaniPeri y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA