找到两个相同大小的数组的元素之间的唯一的对应关系 [英] Find the unique mapping between elements of two same size arrays

问题描述

我最近问在接受采访时这样一个问题：

I was recently asked this question in an interview:

有大小N的每两个阵列。一个阵列具有螺母，另一个具有螺栓。每个螺母完全适合一个螺栓，反之亦然。当你用螺栓比较螺母，你得到的3结果之一：紧，松，配合。

There are two arrays of size 'n' each. One array has nuts, the other one has bolts. Each nut fits exactly one bolt and vice-versa. When you compare a nut with a bolt, you get one of the 3 results: tight,loose,fits.

你如何有效地找到了唯一的对应关系？

How do you efficiently find the unique mapping?

排序是不可能在任一台。你永远不知道，如果B1比B2或
小 N1比N2小。其中n1，n2是坚果和B1，B2是螺栓。你唯一可以做的是用螺栓比较螺母和得到的结果：紧，适合，宽松

Sorting is not possible on either of the sets. You never know if b1 is smaller than b2 or
n1 is smaller than n2. Where n1,n2 are nuts and b1,b2 are bolts. Only thing you can do is compare a nut with a bolt and get a result: tight,fits,loose.

推荐答案

像算法的快速排序做这项工作：

The quicksort like algorithm does the job:

1. 随机挑选一个螺母 N ，并以此为支点划分 B的组船分成三个组：紧（ B1 ），松（ B2 ），配合。
2. 标记配合船为 B 。现在，您使用此船为支点进行分区设置螺母ñ\ñ分为两个组：紧的（ N1 ）或松（ N2 ）。
3. 现在，你有三个对： N1 和 B1 ， N 和 B ， N2 和 B2 。所有这些都是相同大小的。你可以做同样的分区递归的（ N1，B2 ）和（ N2，B1 ），你可以得到的最终的答案。

1. Randomly pick a nut n and use it as pivot to partition the set of boat B into three set: tight (B1), loose (B2), fits.
2. Mark the fit boat as b. Now you use this boat as pivot to partition the nuts set N\n into two set: tight (N1) or loose (N2).
3. Now you have three pairs: N1 and B1, n and b, N2 and B2. All of them are of the same size. You can do the same partitioning recursively on (N1,B2) and (N2,B1) and you can get the final answer.

这是明显的复杂性是 O（N日志N），一样的快速排序。

It is obvious the complexity is O(N log N), the same as quicksort.

这篇关于找到两个相同大小的数组的元素之间的唯一的对应关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！