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. Example Given nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC'].

Your code should find the matching bolts and nuts.

one of the possible return:

nuts = ['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG'].

we will tell you the match compare function. 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.

S: partition型two pointer 因为nuts和bolts内部不能排序，只能取bolts中一个元素作为pivot在nuts中进行快排。quick select得到nuts中pivot对应的元素后，再将次元素作为pivot在bolts中进行快排。这样可以将bolts和nuts分割为两部分（分割好后两pivot的idx相同）。然后在这两部分重复上述步骤。 best case: O(n + n/2 + n/4 + ...) = O(n) worst case: O(n + n-1 + n-2 +...) = O(n^2)

注意次代码会超时，应有死循环未发现 ["a","b"]["B","A"]就会超时
/**
 * class Comparator {
 *     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.
*/
class Solution {
public:
    /**
     * @param nuts: a vector of integers
     * @param bolts: a vector of integers
     * @param compare: a instance of Comparator
     * @return: nothing
     */
    void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
        quickSort(nuts, bolts, compare, 0, nuts.size() - 1);
    }
    void quickSort(vector<string>& nuts, vector<string>& bolts, Comparator compare, 
                   int l, int r) {
        if (l >= r) {
            return;
        }
        int nuts_pidx = partition(nuts, l, r, bolts[l], compare);
        partition(bolts, l, r, nuts[nuts_pidx], compare); //用对应的nuts来partition
        quickSort(nuts, bolts, compare, l, nuts_pidx - 1);
        quickSort(nuts, bolts, compare, nuts_pidx + 1, r);
    }

    int partition(vector<string>& s, int left, int right, string target, Comparator c) {
        int l = left, r = right;
        for (int i = l; i <= r; ++i) {
            if (c.cmp(s[i], target) == 0 || c.cmp(target, s[i]) == 0) {
                string tmp = s[i];
                s[i] = s[l];
                s[l] = tmp;
                break;
            }
        }
        string pivot = s[l];
        while (l < r) {
            while (l < r && (c.cmp(s[r], target) == -1 || c.cmp(target, s[r]) == 1)) {
                r--;
            }
            s[l] = s[r];
            while (l < r && (c.cmp(s[r], target) == 1 || c.cmp(target, s[r]) == -1)) {
                l++;
            }
            s[r] = s[l];
        }
        s[l] = pivot;
        return l;
    }
};