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 una tuerca solo se puede comparar con un perno y un perno solo se puede comparar con una tuerca para ver cuál es más grande o más pequeño.
Otra forma de plantear este problema es dar una caja con candados y llaves donde un candado se puede abrir con una llave en la caja. Tenemos que hacer coincidir la pareja.
Modo de fuerza bruta: Comience con el primer perno y compárelo con cada tuerca hasta que encontremos una coincidencia. En el peor de los casos, requerimos n comparaciones. Hacer esto para todos los tornillos nos da una complejidad O(n^2).
Forma de clasificación rápida: podemos usar la técnica de clasificación rápida para resolver esto. Representamos tuercas y tornillos en una array de caracteres para comprender la lógica.
Nueces representadas como una array de caracteres
char nuts[] = {‘@’, ‘#’, ‘$’, ‘%’, ‘^’, ‘&’}
Tornillos representados como una array de caracteres
char bolts[] = {‘$’, ‘%’, ‘&’, ‘^’, ‘@’, ‘#’}
Este algoritmo primero realiza una partición seleccionando el último elemento de la array de pernos como pivote, reorganizando la array de tuercas y devuelve el índice de partición ‘i’ de modo que todas las tuercas más pequeñas que las tuercas [i] están en el lado izquierdo y todas las tuercas mayores que las nueces[i] están en el lado derecho. Luego, usando las tuercas [i], podemos dividir la array de tornillos. Las operaciones de particionamiento se pueden implementar fácilmente en O(n). Esta operación también hace que la array de tuercas y tornillos esté bien dividida. Ahora aplicamos esta partición recursivamente en el subconjunto izquierdo y derecho de tuercas y tornillos.
A medida que aplicamos la partición en tuercas y tornillos, ¿será la complejidad del tiempo total? (2*nlogn) = (nlogn) en promedio.
Aquí, en aras de la simplicidad, hemos elegido el último elemento siempre como pivote. También podemos hacer una ordenación rápida aleatoria.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to solve nut and bolt
// problem using Quick Sort.
#include <iostream>
using namespace std;
// Method to print the array
void printArray(char arr[])
{
for(int i = 0; i < 6; i++)
{
cout << " " << arr[i];
}
cout << "\n";
}
// Similar to standard partition method.
// Here we pass the pivot element too
// instead of choosing it inside the method.
int partition(char arr[], int low,
int high, char pivot)
{
int i = low;
char temp1, temp2;
for(int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
temp1 = arr[i];
arr[i] = arr[j];
arr[j] = temp1;
i++;
}
else if(arr[j] == pivot)
{
temp1 = arr[j];
arr[j] = arr[high];
arr[high] = temp1;
j--;
}
}
temp2 = arr[i];
arr[i] = arr[high];
arr[high] = temp2;
// Return the partition index of
// an array based on the pivot
// element of other array.
return i;
}
// Function which works just like quick sort
void matchPairs(char nuts[], char bolts[],
int low, int high)
{
if (low < high)
{
// Choose last character of bolts
// array for nuts partition.
int pivot = partition(nuts, low,
high, bolts[high]);
// Now using the partition of nuts
// choose that for bolts partition.
partition(bolts, low, high, nuts[pivot]);
// Recur for [low...pivot-1] &
// [pivot+1...high] for nuts and
// bolts array.
matchPairs(nuts, bolts, low, pivot - 1);
matchPairs(nuts, bolts, pivot + 1, high);
}
}
// Driver code
int main()
{
// Nuts and bolts are represented
// as array of characters
char nuts[] = {'@', '#', '$', '%', '^', '&'};
char bolts[] = {'$', '%', '&', '^', '@', '#'};
// Method based on quick sort which
// matches nuts and bolts
matchPairs(nuts, bolts, 0, 5);
cout <<"Matched nuts and bolts are : \n";
printArray(nuts);
printArray(bolts);
}
// This code is contributed by shivanisinghss2110
C
// C program to solve nut and bolt
// problem using Quick Sort.
#include<stdio.h>
// Method to print the array
void printArray(char arr[])
{
for(int i = 0; i < 6; i++)
{
printf("%c ", arr[i]);
}
printf("\n");
}
// Similar to standard partition method.
// Here we pass the pivot element too
// instead of choosing it inside the method.
int partition(char arr[], int low,
int high, char pivot)
{
int i = low;
char temp1, temp2;
for(int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
temp1 = arr[i];
arr[i] = arr[j];
arr[j] = temp1;
i++;
}
else if(arr[j] == pivot)
{
temp1 = arr[j];
arr[j] = arr[high];
arr[high] = temp1;
j--;
}
}
temp2 = arr[i];
arr[i] = arr[high];
arr[high] = temp2;
// Return the partition index of
// an array based on the pivot
// element of other array.
return i;
}
// Function which works just like quick sort
void matchPairs(char nuts[], char bolts[],
int low, int high)
{
if (low < high)
{
// Choose last character of bolts
// array for nuts partition.
int pivot = partition(nuts, low,
high, bolts[high]);
// Now using the partition of nuts
// choose that for bolts partition.
partition(bolts, low, high, nuts[pivot]);
// Recur for [low...pivot-1] &
// [pivot+1...high] for nuts and
// bolts array.
matchPairs(nuts, bolts, low, pivot - 1);
matchPairs(nuts, bolts, pivot + 1, high);
}
}
// Driver code
int main()
{
// Nuts and bolts are represented
// as array of characters
char nuts[] = {'@', '#', '$', '%', '^', '&'};
char bolts[] = {'$', '%', '&', '^', '@', '#'};
// Method based on quick sort which
// matches nuts and bolts
matchPairs(nuts, bolts, 0, 5);
printf("Matched nuts and bolts are : \n");
printArray(nuts);
printArray(bolts);
}
// This code is contributed by Amit Mangal.
Java
// Java program to solve nut and bolt problem using Quick Sort
public class NutsAndBoltsMatch
{
//Driver method
public static void main(String[] args)
{
// Nuts and bolts are represented as array of characters
char nuts[] = {'@', '#', '$', '%', '^', '&'};
char bolts[] = {'$', '%', '&', '^', '@', '#'};
// Method based on quick sort which matches nuts and bolts
matchPairs(nuts, bolts, 0, 5);
System.out.println("Matched nuts and bolts are : ");
printArray(nuts);
printArray(bolts);
}
// Method to print the array
private static void printArray(char[] arr) {
for (char ch : arr){
System.out.print(ch + " ");
}
System.out.print("\n");
}
// Method which works just like quick sort
private static void matchPairs(char[] nuts, char[] bolts, int low,
int high)
{
if (low < high)
{
// Choose last character of bolts array for nuts partition.
int pivot = partition(nuts, low, high, bolts[high]);
// Now using the partition of nuts choose that for bolts
// partition.
partition(bolts, low, high, nuts[pivot]);
// Recur for [low...pivot-1] & [pivot+1...high] for nuts and
// bolts array.
matchPairs(nuts, bolts, low, pivot-1);
matchPairs(nuts, bolts, pivot+1, high);
}
}
// Similar to standard partition method. Here we pass the pivot element
// too instead of choosing it inside the method.
private static int partition(char[] arr, int low, int high, char pivot)
{
int i = low;
char temp1, temp2;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot){
temp1 = arr[i];
arr[i] = arr[j];
arr[j] = temp1;
i++;
} else if(arr[j] == pivot){
temp1 = arr[j];
arr[j] = arr[high];
arr[high] = temp1;
j--;
}
}
temp2 = arr[i];
arr[i] = arr[high];
arr[high] = temp2;
// Return the partition index of an array based on the pivot
// element of other array.
return i;
}
}
Python3
# Python program to solve nut and bolt
# problem using Quick Sort.
from typing import List
# Method to print the array
def printArray(arr: List[str]) -> None:
for i in range(6):
print(" {}".format(arr[i]), end=" ")
print()
# Similar to standard partition method.
# Here we pass the pivot element too
# instead of choosing it inside the method.
def partition(arr: List[str], low: int, high: int, pivot: str) -> int:
i = low
j = low
while j < high:
if (arr[j] < pivot):
arr[i], arr[j] = arr[j], arr[i]
i += 1
elif (arr[j] == pivot):
arr[j], arr[high] = arr[high], arr[j]
j -= 1
j += 1
arr[i], arr[high] = arr[high], arr[i]
# Return the partition index of
# an array based on the pivot
# element of other array.
return i
# Function which works just like quick sort
def matchPairs(nuts: List[str], bolts: List[str], low: int, high: int) -> None:
if (low < high):
# Choose last character of bolts
# array for nuts partition.
pivot = partition(nuts, low, high, bolts[high])
# Now using the partition of nuts
# choose that for bolts partition.
partition(bolts, low, high, nuts[pivot])
# Recur for [low...pivot-1] &
# [pivot+1...high] for nuts and
# bolts array.
matchPairs(nuts, bolts, low, pivot - 1)
matchPairs(nuts, bolts, pivot + 1, high)
# Driver code
if __name__ == "__main__":
# Nuts and bolts are represented
# as array of characters
nuts = ['@', '#', '$', '%', '^', '&']
bolts = ['$', '%', '&', '^', '@', '#']
# Method based on quick sort which
# matches nuts and bolts
matchPairs(nuts, bolts, 0, 5)
print("Matched nuts and bolts are : ")
printArray(nuts)
printArray(bolts)
# This code is contributed by sanjeev2552
C#
// C# program to solve nut and
// bolt problem using Quick Sort
using System;
using System.Collections.Generic;
class GFG
{
// Driver Code
public static void Main(String[] args)
{
// Nuts and bolts are represented
// as array of characters
char []nuts = {'@', '#', '$', '%', '^', '&'};
char []bolts = {'$', '%', '&', '^', '@', '#'};
// Method based on quick sort
// which matches nuts and bolts
matchPairs(nuts, bolts, 0, 5);
Console.WriteLine("Matched nuts and bolts are : ");
printArray(nuts);
printArray(bolts);
}
// Method to print the array
private static void printArray(char[] arr)
{
foreach (char ch in arr)
{
Console.Write(ch + " ");
}
Console.Write("\n");
}
// Method which works just like quick sort
private static void matchPairs(char[] nuts,
char[] bolts,
int low, int high)
{
if (low < high)
{
// Choose last character of
// bolts array for nuts partition.
int pivot = partition(nuts, low,
high, bolts[high]);
// Now using the partition of nuts
// choose that for bolts partition.
partition(bolts, low, high, nuts[pivot]);
// Recur for [low...pivot-1] &
// [pivot+1...high] for nuts
// and bolts array.
matchPairs(nuts, bolts, low, pivot - 1);
matchPairs(nuts, bolts, pivot + 1, high);
}
}
// Similar to standard partition method.
// Here we pass the pivot element too
// instead of choosing it inside the method.
private static int partition(char[] arr, int low,
int high, char pivot)
{
int i = low;
char temp1, temp2;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
temp1 = arr[i];
arr[i] = arr[j];
arr[j] = temp1;
i++;
}
else if(arr[j] == pivot)
{
temp1 = arr[j];
arr[j] = arr[high];
arr[high] = temp1;
j--;
}
}
temp2 = arr[i];
arr[i] = arr[high];
arr[high] = temp2;
// Return the partition index of an array
// based on the pivot element of other array.
return i;
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to solve nut and
// bolt problem using Quick Sort
// Method to print the array
function printArray(arr)
{
for (let ch = 0 ; ch < arr.length ; ch++)
{
document.write(arr[ch] + " ");
}
document.write("<br>");
}
// Method which works just like quick sort
function matchPairs( nuts, bolts, low, high)
{
if (low < high)
{
// Choose last character of
// bolts array for nuts partition.
var pivot = partition(nuts, low,
high, bolts[high]);
// Now using the partition of nuts
// choose that for bolts partition.
partition(bolts, low, high, nuts[pivot]);
// Recur for [low...pivot-1] &
// [pivot+1...high] for nuts
// and bolts array.
matchPairs(nuts, bolts, low, pivot - 1);
matchPairs(nuts, bolts, pivot + 1, high);
}
}
// Similar to standard partition method.
// Here we pass the pivot element too
// instead of choosing it inside the method.
function partition( arr, low, high, pivot)
{
var i = low;
var temp1, temp2;
for (var j = low; j < high; j++)
{
if (arr[j] < pivot)
{
temp1 = arr[i];
arr[i] = arr[j];
arr[j] = temp1;
i++;
}
else if(arr[j] == pivot)
{
temp1 = arr[j];
arr[j] = arr[high];
arr[high] = temp1;
j--;
}
}
temp2 = arr[i];
arr[i] = arr[high];
arr[high] = temp2;
// Return the partition index of an array
// based on the pivot element of other array.
return i;
}
// Driver Code
// Nuts and bolts are represented
// as array of characters
var nuts = ['@', '#', '$', '%', '^', '&'];
var bolts = ['$', '%', '&', '^', '@', '#'];
// Method based on quick sort
// which matches nuts and bolts
matchPairs(nuts, bolts, 0, 5);
document.write(
"Matched nuts and bolts are : " + "<br>"
);
printArray(nuts);
printArray(bolts);
</script>
Producción:
Matched nuts and bolts are : # $ % & @ ^ # $ % & @ ^
Complejidad de tiempo: O(N*logN), ya que estamos usando un bucle para atravesar N veces en la función de partición, por lo que cuesta O(N) tiempo y estamos llamando a la función de partición en cada llamada recursiva de la función matchPairs que cuesta O( logN) tiempo como en la llamada recursiva dividimos la array por la mitad. Donde N es la longitud de la string.
Espacio auxiliar: O(logN)
Problema de tuercas y pernos (problema de cerradura y llave) | Conjunto 2 (Hashmap)
Este artículo es una contribución de Kumar Gautam . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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