Dado un conjunto de n tuercas de diferentes tamaños y n pernos de diferentes tamaños. Hay un mapeo uno a uno entre tuercas y tornillos. Haga coincidir tuercas y tornillos de manera eficiente.
Restricción: No se permite la comparación de una tuerca con otra tuerca o un perno con otro perno. Significa que la tuerca solo se puede comparar con el perno y el perno solo se puede comparar con una tuerca para ver cuál es más grande o más pequeño.
Ejemplos:
Input : nuts[] = {'@', '#', '$', '%', '^', '&'}
bolts[] = {'$', '%', '&', '^', '@', '#'}
Output : Matched nuts and bolts are-
$ % & ^ @ #
$ % & ^ @ #
Otra forma de plantear este problema es, dada una caja con cerraduras y llaves donde una cerradura puede abrirse con una llave en la caja. Tenemos que hacer coincidir la pareja.
Hemos discutido una solución basada en clasificación debajo de la publicación.
Problema de tuercas y pernos (problema de cerradura y llave) | Serie 1
En esta publicación, se analiza el enfoque basado en hashmap.
- Atraviesa la array de nueces y crea un mapa hash
- Recorra la array de pernos y búsquela en hashmap.
- Si se encuentra en el mapa hash de nueces, significa que existen pernos para esa tuerca.
Implementación:
C++
// Hashmap based solution to solve
#include <bits/stdc++.h>
using namespace std;
// function to match nuts and bolts
void nutboltmatch(char nuts[], char bolts[], int n)
{
unordered_map<char, int> hash;
// creating a hashmap for nuts
for (int i = 0; i < n; i++)
hash[nuts[i]] = i;
// searching for nuts for each bolt in hash map
for (int i = 0; i < n; i++)
if (hash.find(bolts[i]) != hash.end())
nuts[i] = bolts[i];
// print the result
cout << "matched nuts and bolts are-" << endl;
for (int i = 0; i < n; i++)
cout << nuts[i] << " ";
cout << endl;
for (int i = 0; i < n; i++)
cout << bolts[i] << " ";
}
// Driver code
int main()
{
char nuts[] = {'@', '#', '$', '%', '^', '&'};
char bolts[] = {'$', '%', '&', '^', '@', '#'};
int n = sizeof(nuts) / sizeof(nuts[0]);
nutboltmatch(nuts, bolts, n);
return 0;
}
Java
// Hashmap based solution to solve
import java.util.HashMap;
class GFG
{
// function to match nuts and bolts
static void nutboltmatch(char nuts[], char bolts[], int n)
{
HashMap<Character, Integer> hash = new HashMap<>();
// creating a hashmap for nuts
for (int i = 0; i < n; i++)
hash.put(nuts[i], i);
// searching for nuts for each bolt in hash map
for (int i = 0; i < n; i++)
if (hash.containsKey(bolts[i]))
nuts[i] = bolts[i];
// print the result
System.out.println("matched nuts and bolts are-");
for (int i = 0; i < n; i++)
System.out.print(nuts[i] + " ");
System.out.println();
for (int i = 0; i < n; i++)
System.out.print(bolts[i] + " ");
}
// Driver code
public static void main(String[] args)
{
char nuts[] = { '@', '#', '$', '%', '^', '&' };
char bolts[] = { '$', '%', '&', '^', '@', '#' };
int n = nuts.length;
nutboltmatch(nuts, bolts, n);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program to implement
# above approach
# Hashmap based solution to
# solve
# Function to match nuts and
# bolts
def nutboltmatch(nuts,
bolts, n):
hash1 = {}
# creating a hashmap
# for nuts
for i in range(n):
hash1[nuts[i]] = i
# searching for nuts for
# each bolt in hash map
for i in range(n):
if (bolts[i] in hash1):
nuts[i] = bolts[i]
# Print the result
print("matched nuts and bolts are-")
for i in range(n):
print(nuts[i],
end = " ")
print()
for i in range(n):
print(bolts[i],
end = " ")
# Driver code
if __name__ == "__main__":
nuts = ['@', '#', '$',
'%', '^', '&']
bolts = ['$', '%', '&',
'^', '@', '#']
n = len(nuts)
nutboltmatch(nuts, bolts, n)
# This code is contributed by Chitranayal
C#
// Hashmap based solution to solve
using System;
using System.Collections.Generic;
public class GFG
{
// function to match nuts and bolts
static void nutboltmatch(char[] nuts, char[] bolts, int n)
{
Dictionary<char,int> hash = new Dictionary<char,int>();
// creating a hashmap for nuts
for (int i = 0; i < n; i++)
{
hash.Add(nuts[i], i);
}
// searching for nuts for each bolt in hash map
for (int i = 0; i < n; i++)
if (hash.ContainsKey(bolts[i]))
nuts[i] = bolts[i];
// print the result
Console.WriteLine("matched nuts and bolts are-");
for (int i = 0; i < n; i++)
Console.Write(nuts[i] + " ");
Console.WriteLine();
for (int i = 0; i < n; i++)
Console.Write(bolts[i] + " ");
}
// Driver code
static public void Main ()
{
char[] nuts = { '@', '#', '$', '%', '^', '&' };
char[] bolts = { '$', '%', '&', '^', '@', '#' };
int n = nuts.Length;
nutboltmatch(nuts, bolts, n);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Hashmap based solution to solve
// function to match nuts and bolts
function nutboltmatch(nuts, bolts, n) {
let hash = new Map();
// creating a hashmap for nuts
for (let i = 0; i < n; i++)
hash.set(nuts[i], i);
// searching for nuts for each bolt in hash map
for (let i = 0; i < n; i++)
if (hash.has(bolts[i]))
nuts[i] = bolts[i];
// print the result
document.write("matched nuts and bolts are-<br>");
for (let i = 0; i < n; i++)
document.write(nuts[i] + " ");
document.write("<br>");
for (let i = 0; i < n; i++)
document.write(bolts[i] + " ");
}
// Driver code
let nuts = ['@', '#', '$', '%', '^', '&'];
let bolts = ['$', '%', '&', '^', '@', '#'];
let n = nuts.length;
nutboltmatch(nuts, bolts, n);
</script>
matched nuts and bolts are- $% & ^ @ # $% & ^ @ #
La complejidad temporal de esta solución es O(n).
Este artículo es una contribución de Niteesh kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA