【C#】螺钉和螺母问题

螺钉与螺母问题

做题时，遇到了这个问题，顺手记录一下。(～￣▽￣)～

问题描述

假设我们有n个直径各不相同的螺钉以及n个相应的螺母。我们一次只能比较一对螺钉和螺母，来判断螺母是大于螺钉 、小于螺钉还是正好适合螺钉。然而，我们不能拿两个螺母作比较，也不能拿两个螺钉作比较。我们的问题是要找到每一对匹配的螺钉和螺母。为该问题设计一个算法，它的平均效率必须属于集合θ(nlogn)。

思路

这个问题比较迷惑的地方就是螺母之间、螺钉之间不能比较。但说真的，螺钉是与螺母是相互对应的，螺钉与螺母比实际上就可以看做是螺母之间在比。nlogn又让人想到快排，很明显这就是是两组快排。

1. 从螺钉中选出一个，对螺母们进行划分成三部分，比这个螺钉小的、大的和相等的。
2. 取出第一步相等的螺母，对螺钉们进行相同的划分。
3. 对小的部分，和大的部分，进行递归操作。

代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace ZExercise
{ class Program{static void Swap(ref int[]a  ,int i ,int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}static int Sort(ref int[] a, ref int i, ref int j, int pivot){while (i < j) //这里按照题目，是n个直径各不相同的螺钉，否则无法跳出循环{while (a[i] < pivot) { i++; }while (a[j] > pivot) { j--; } Swap(ref a, i, j);  }i++;j--;return a[i - 1];}static void Match(ref int[] nuts,ref int[] bolts,int low ,int high) {int pivot = nuts[ (low + high )/2]; int i = low;int j = high; int mbolt = Sort(ref bolts,ref i, ref j,pivot);// 利用螺母找螺钉，并划分成三部分pivot = mbolt;//用找到螺钉作为枢纽i = low;j = high;Sort(ref nuts, ref i, ref j, pivot);// 利用螺钉找螺母，并划分成三部分if (i < high) { Match(ref nuts,ref bolts,i ,high); }if (j > low) { Match(ref nuts, ref bolts, low, j); }}static void Show(int[] a,int len) {for (int i = 0; i < len; i++){Console.Write(a[i] + " ");}Console.WriteLine("");}static void Main(string[] args){int[] nuts = { 0,2,1,10,3,4,13,9,8,6};int[] bolts = { 13,4,3,2,6,10,1,9,8,0};Match(ref nuts,ref bolts,0,9);Console.WriteLine("nuts:");Show(nuts,10);Console.WriteLine("bolts:");Show(bolts, 10);Console.ReadKey();}}
}

运行结果

水平有限，如有错误，请多包涵 (〃‘▽’〃)