|锁紧螺栓和锁紧螺母问题1-yiteyi-C++库

给定一组不同尺寸的n个螺母和n个不同尺寸的螺栓。螺母和螺栓之间存在一一对应关系。有效地匹配螺母和螺栓。 限制条件： 不允许将一个螺母与另一个螺母或螺栓与另一个螺栓进行比较。这意味着螺母只能与螺栓进行比较，螺栓只能与螺母进行比较，以确定哪个更大/更小。问这个问题的另一种方式是，给定一个带锁和钥匙的盒子，盒子里的一把钥匙可以打开一把锁。我们需要配对。

null

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

暴力方式： 从第一个螺栓开始，将其与每个螺母进行比较，直到找到匹配的螺栓。在最坏的情况下，我们需要n个比较。对所有螺栓执行此操作会给我们带来O（n^2）复杂性。 快速分拣方式： 我们可以使用快速排序技术来解决这个问题。为了理解逻辑，我们在字符数组中表示螺母和螺栓。表示为字符数组的螺母 char nuts[]={‘@’、’#’、’$’、’%’、’^’、’&’} 表示为字符数组的螺栓 char bolts[]={‘$’、’%’、’&’、’^’、’@’、’#’} 该算法首先通过选取螺栓数组的最后一个元素作为枢轴来执行分区，重新排列螺母数组，并返回分区索引“i”，以便所有小于螺母[i]的螺母位于左侧，而所有大于螺母[i]的螺母位于右侧。接下来使用螺母[i]我们可以划分螺栓阵列。分区操作可以很容易地在O（n）中实现。此操作还可以使螺母和螺栓阵列很好地分区。现在，我们将这种划分递归地应用于螺母和螺栓的左、右子数组。当我们在螺母和螺栓上应用分区时，总的时间复杂度会是多少？（2*nlogn）=？（nlogn）平均值。为了简单起见，我们选择了最后一个元素始终作为轴心。我们也可以做随机快速排序。以下是上述理念的实施情况：

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 <<                                     ""                                     ;                       
                         }                       
           
                         // 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 : "                                     ;                       
                                   
                                                 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                                     (                                     ""                                     );                       
                         }                       
           
                         // 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 : "                                     );                       
                                   
                                                 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(                                     ""                                     );                       
                                                 }                       
           
                                                 // 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(                                     ""                                     );                       
                                                 }                       
           
                                                 // 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>                       

输出：

Matched nuts and bolts are :# $ % & @ ^# $ % & @ ^

螺母和螺栓问题（锁和钥匙问题）|集合2（Hashmap）本文由 库马尔·戈塔姆 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章