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.
Example
Given nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC'].
Your code should find the matching bolts and nuts.
public class Solution {
/**
* @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;
}
private void swap(String[] str, int l, int r) {
String temp = str[l];
str[l] = str[r];
str[r] = temp;
}
}
Another Way of Partition
/**
* 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.
*/
public class Solution {
/**
* @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;
}
int totalLength = nuts.length;
qsort(nuts, bolts, 0, totalLength - 1, compare);
}
public void qsort(String[] nuts, String[] bolts, int l, int r, NBComparator compare) {
if (l >= r) {
return;
}
// Find partition index for nuts, with bolts[l]
int partIndex = partition(nuts, bolts[l], l, r, compare);
// Partition bolts, with nuts[partIndex]
partition(bolts, nuts[partIndex], l, r, compare);
// quick sort recursively
qsort(nuts, bolts, l, partIndex - 1, compare);
qsort(nuts, bolts, partIndex + 1, r, compare);
}
public int partition(String[] arr, String pivot, int l, int r, NBComparator compare) {
// pivot is from another array
int m = l;
for (int i = l + 1; i <= r; i++) {
if (compare.cmp(arr[i], pivot) == -1 || compare.cmp(pivot, arr[i]) == 1) {
m++;
swap(arr, i, m);
} else if (compare.cmp(arr[i], pivot) == 0 || compare.cmp(pivot, arr[i]) == 0) {
swap(arr, i, l);
i--;
}
}
swap(arr, m, l);
return m;
}
public void swap(String[] arr, int l, int r) {
String temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
}