https://www.lintcode.com/problem/nuts-bolts-problem/description
https://www.jianshu.com/p/f4f24c25d109
https://www.jiuzhang.com/solutions/nuts-bolts-problem/
Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts.
Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller. We will give you a compare function to compare nut with bolt.
Using the function we give you, you are supposed to sort nuts or bolts, so that they can map in order.
Example
Given nuts =
['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC'].
Your code should find the matching of bolts and nuts.
According to the function, one of the possible return:
nuts =
['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG'].
If we give you another compare function, the possible return is the following:
nuts =
['ab','bc','dd','gg'], bolts = ['BC','AA','DD','GG'].
So you must use the compare function that we give to do the sorting.
The order of the nuts or bolts does not matter. You just need to find the matching bolt for each nut.
螺帽螺母问题脱胎于排序问题，这里的特别之处在于需要通过两个array进行对应的排序。这就需要利用一个array中的元素对另一个array进行partition，并反过来重复这一个过程，最终让两个array都满足comparator所定义的相同顺序。
这里要注意的是partition的变式，因为pivot并非来源当前array，只能通过一方元素作为基准，对另一个array进行partition。
核心在于：首先使用 nuts 中的某一个元素作为基准对 bolts 进行 partition 操作，随后将 bolts 中得到的基准元素作为基准对 nuts 进行 partition 操作。
https://algorithm.yuanbin.me/zh-hans/problem_misc/nuts_and_bolts_problem.html这里要注意的是partition的变式，因为pivot并非来源当前array，只能通过一方元素作为基准，对另一个array进行partition。
核心在于：首先使用 nuts 中的某一个元素作为基准对 bolts 进行 partition 操作，随后将 bolts 中得到的基准元素作为基准对 nuts 进行 partition 操作。
首先结合例子读懂题意，本题为 nuts 和 bolts 的配对问题，但是需要根据题目所提供的比较函数，且 nuts 与 nuts 之间的元素无法直接比较，compare 仅能在 nuts 与 bolts 之间进行。首先我们考虑若没有比较函数的限制，那么我们可以分别对 nuts 和 bolts 进行排序，由于是一一配对，故排完序后即完成配对。那么在只能通过比较对方元素得知相对大小时怎么完成排序呢？
我们容易通过以一组元素作为参考进行遍历获得两两相等的元素，这样一来在最坏情况下时间复杂度为 , 相当于冒泡排序。根据排序算法理论可知基于比较的排序算法最好的时间复杂度为 , 也就是说这道题应该是可以进一步优化。回忆一些基于比较的排序算法，能达到 时间复杂度的有堆排、归并排序和快速排序，由于这里只能通过比较得到相对大小的关系，故可以联想到快速排序。
快速排序的核心即为定基准，划分区间。由于这里只能以对方的元素作为基准，故一趟划分区间后仅能得到某一方基准元素排序后的位置，那通过引入 的额外空间来对已处理的基准元素进行标记如何呢？这种方法实现起来较为困难，因为只能对一方的元素划分区间，而对方的元素无法划分区间进而导致递归无法正常进行。
山穷水尽疑无路，柳暗花明又一村。由于只能通过对方进行比较，故需要相互配合进行 partition 操作(这个点确实难以想到)。核心在于：首先使用 nuts 中的某一个元素作为基准对 bolts 进行 partition 操作，随后将 bolts 中得到的基准元素作为基准对 nuts 进行 partition 操作。
Quick Sort Way: We can use quick sort technique to solve this. We represent nuts and bolts in character array for understanding the logic.
Nuts represented as array of character
char nuts[] = {‘@’, ‘#’, ‘$’, ‘%’, ‘^’, ‘&’}
char nuts[] = {‘@’, ‘#’, ‘$’, ‘%’, ‘^’, ‘&’}
Bolts represented as array of character
char bolts[] = {‘$’, ‘%’, ‘&’, ‘^’, ‘@’, ‘#’}
char bolts[] = {‘$’, ‘%’, ‘&’, ‘^’, ‘@’, ‘#’}
This algorithm first performs a partition by picking last element of bolts array as pivot, rearrange the array of nuts and returns the partition index ‘i’ such that all nuts smaller than nuts[i] are on the left side and all nuts greater than nuts[i] are on the right side. Next using the nuts[i] we can partition the array of bolts. Partitioning operations can easily be implemented in O(n). This operation also makes nuts and bolts array nicely partitioned. Now we apply this partitioning recursively on the left and right sub-array of nuts and bolts.
As we apply partitioning on nuts and bolts both so the total time complexity will be Θ(2*nlogn) = Θ(nlogn) on average.
Partition function类似sort colors
nuts和bolts数组内的元素是一一对应的. 并且元素之间是有大小关系的.
题意可以这么理解: nuts是一个排列, bolts也是一个排列, 需要把它们变成同一个排列(不一定是升序排列或降序),
但是我们仅仅可以比较nuts的某个元素和bolts的某个元素.
我们同时将两个数组都排成升序以让它们满足按照顺序一一对应的关系.
排序的过程类似快速排序.
定义
quickSort(nuts, bolts, l, r, compare)为将两个数组的[l, r]区间排好序- 选取比如nuts[l]作为pivot, 将bolts数组根据pivot做好划分(比它小的在左边, 比它大的在右边)
- 因为只能借助对方数组的元素进行比较, 所以此时借用bolts内的该值对nuts再进行一次划分
- 递归处理左右子区间
关键在于2, 如果没有这一步, 那么nuts不会变成有序的. 最终也无法按照顺序一一对应
* public class NBCompare {
* public int cmp(String a, String b);
* }
* You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
* if "a" is bigger than "b", it will return 1, else if they are equal,
* it will return 0, else if "a" is smaller than "b", it will return -1.
* When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
* @param nuts: an array of integers
* @param bolts: an array of integers
* @param compare: a instance of Comparator
* @return: nothing
public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
if (nuts == null || bolts == null) return;
if (nuts.length != bolts.length) return;
qsort(nuts, bolts, compare, 0, nuts.length - 1);
}
private void qsort(String[] nuts, String[] bolts, NBComparator compare,
int l, int u) {
if (l >= u) return;
// find the partition index for nuts with bolts[l]
int part_inx = partition(nuts, bolts[l], compare, l, u);
// partition bolts with nuts[part_inx]
partition(bolts, nuts[part_inx], compare, l, u);
// qsort recursively
qsort(nuts, bolts, compare, l, part_inx - 1);
qsort(nuts, bolts, compare, part_inx + 1, u);
}
private int partition(String[] str, String pivot, NBComparator compare,
int l, int u) {
for (int i = l; i <= u; i++) {
if (compare.cmp(str[i], pivot) == 0 ||
compare.cmp(pivot, str[i]) == 0) {
swap(str, i, l);
break;
}
}
String now = str[l];
int left = l;
int right = u;
while (left < right) {
while (left < right &&
(compare.cmp(str[right], pivot) == 1 ||
compare.cmp(pivot, str[right]) == -1)) {
right--;
}
str[left] = str[right];
while (left < right &&
(compare.cmp(str[left], pivot) == -1 ||
compare.cmp(pivot, str[left]) == 1)) {
left++;
}
str[right] = str[left];
}
str[left] = now;
return left;
}
Nuts and bolts. A disorganized carpenter has a mixed pile of n nuts and n bolts. The goal is to find the corresponding pairs of nuts and bolts. Each nut fits exactly one bolt and each bolt fits exactly one nut. By fitting a nut and a bolt together, the carpenter can see which one is bigger (but the carpenter cannot compare two nuts or two bolts directly). Design an algorithm for the problem that uses nlogn compares (probabilistically).
分析：
题意是有一堆螺帽和螺钉，分别为n个，每个螺帽只可能和一个螺钉配对，目标是找出配对的螺帽和螺钉。螺帽和螺钉的是否配对只能通过螺帽和螺钉比较，不能通过两个螺帽或两个螺钉的比较来判断。比较次数要求限制在nlogn次
设计过程中思考了如下几个问题：
1. 螺帽和螺钉的配对怎么判断？
-螺帽和螺钉分别设计成不同的对象，每个对象都有个size属性，通过判断不同对象的size是否相等来判断是否配对
2. 为什么不能通过把螺帽和螺钉分别排序，然后对应位置一一配对的方式进行设计？
-假如那堆螺帽和螺钉中分别有落单的不能配对的，这种排序后靠位置来匹配的配对方式就明显不合适了，也就是说这种做法鲁棒性太差
3. 既然不能分别排序，那采用把螺帽和螺钉混在一起排序的方式如何？
-恩，貌似可行，但遇到螺帽和螺钉中分别有落单的不能配对的情况，我怎么判断某个位置i处元素是与i-1处的元素配对？还是与i+1处的元素配对？还是i处元素落单呢？
综上几个问题考虑之后，决定如下设计：
a. 现将螺帽进行快速排序，复杂度nlogn
b. 逐个遍历螺钉组中的每个螺钉，在已排序的螺帽中，采用二分查找的方法查找其配对的螺帽。比较次数nlogn，满足题目要求
13 Map<Nut, Bolt> pairs = new HashMap<Nut, Bolt>(); // 存储配对的螺帽和螺丝对 14 Nut[] nuts; 15 Bolt[] bolts; 16 int n; 17 18 public NutsAndBolts(Nut[] nuts, Bolt[] bolts, int n) { 19 this.nuts = nuts; 20 this.bolts = bolts; 21 this.n = n; 22 } 23 24 private int compare(NBParent v, NBParent w) { 25 int vsize = v.getSize(); 26 int wsize = w.getSize(); 27 if (vsize == wsize) return 0; 28 else if (vsize > wsize) return 1; 29 else return -1; 30 } 31 private void exch(NBParent[] nb, int i, int j){ 32 NBParent t = nb[i]; 33 nb[i]=nb[j]; 34 nb[j]=t; 35 } 36 37 public Map<Nut, Bolt> findPairs() { 38 sort(bolts,0,n-1); //先对bolts进行快速排序 39 for(int i = 0; i<n;i++){ //遍历nuts，并在bolts中寻找其成对的bolt 40 Nut nut = nuts[i]; 41 Bolt bolt= findBolt(nut); 42 if(bolt != null) 43 pairs.put(nut, bolt); 44 } 45 return pairs; 46 } 47 private Bolt findBolt(Nut nut){ //在排好序的bolts中二分查找nut 48 int lo = 0; 49 int hi = n-1; 50 while(lo<=hi){ 51 int mid = lo+(hi-lo)/2; 52 int cr = compare(bolts[mid],nut); 53 if(cr<0) lo = mid+1; 54 else if(cr>0) hi = mid-1; 55 else return bolts[mid]; 56 } 57 return null; 58 } 59 private void sort(NBParent[] nb, int lo, int hi){ 60 if(hi<=lo) return; 61 int j = partition(nb,lo,hi); 62 sort(nb,lo,j-1); 63 sort(nb,j+1,hi); 64 } 65 66 private int partition(NBParent[] nb, int lo, int hi){ 67 int i = lo; 68 int j = hi+1; 69 NBParent v = nb[lo]; 70 while(true){ 71 while(compare(nb[++i],v)<0) if(i==hi) break; 72 while(compare(nb[--j],v)>0) if(j==lo) break; 73 if(i>=j) break; 74 exch(nb,i,j); 75 } 76 exch(nb,lo,j); 77 return j; 78 }
