Nuts & Bolts Problem
Written on October 21, 2015
Tweet
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.
public class Solution {
public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
if (nuts == null || bolts == null) return;
int m = nuts.length, n = bolts.length;
if (m != n || m == 0 || n == 0) return;
quickSort(nuts, bolts, compare, 0, m - 1);
}
public void quickSort(String[] nuts, String[] bolts, NBComparator compare, int start, int end) {
if (start >= end) return;
int index = partition(nuts, bolts[start], compare, start, end);
partition(bolts, nuts[index], compare, start, end);
quickSort(nuts, bolts, compare, start, index - 1);
quickSort(nuts, bolts, compare, index + 1, end);
}
public int partition(String[] strings, String pivot, NBComparator compare, int start, int end) {
int index = start;//store for return value
for (int i = start + 1; i <= end; i++) {
if (compare.cmp(pivot, strings[i]) == 1 || compare.cmp(strings[i], pivot) == -1) {
swap(strings, ++ index, i);//exchange small and large values
} else if (compare.cmp(pivot, strings[i]) == 0 || compare.cmp(strings[i], pivot) == 0) {
swap(strings, start, i);
//put strings[i] with real pivot value to start position
i--;//the value used to be in start index, which is not checked yet
}
}
swap(strings, index, start);//put pivot to the correct index
return index;
}
public void swap(String[] strings, int a, int b) {
String temp = strings[a];
strings[a] = strings[b];
strings[b] = temp;
}
};//http://algorithm.yuanbin.me/zh-cn/problem_misc/nuts_and_bolts_problem.html