Nuts 和 Bolts 的问题

描述

给定一组 n 个不同大小的 nuts 和 n 个不同大小的 bolts。nuts 和 bolts 一一匹配。 不允许将 nut 之间互相比较，也不允许将 bolt 之间互相比较。也就是说，只许将 nut 与 bolt 进行比较， 或将 bolt 与 nut 进行比较。请比较 nut 与 bolt 的大小。

您在真实的面试中是否遇到过这个题？   是

样例

给出 nuts = ['ab','bc','dd','gg'], bolts = ['AB','GG', 'DD', 'BC']
你的程序应该找出bolts和nuts的匹配。
一组可能的返回结果是：
nuts = ['ab','bc','dd','gg'], bolts = ['AB','BC','DD','GG']
我们将给你一个匹配的比较函数，如果我们给你另外的比较函数，可能返回的结果是：
nuts = ['ab','bc','dd','gg'], bolts = ['BC','AB','DD','GG']

因此的结果完全取决于比较函数，而不是字符串本身。
因为你必须使用比较函数来进行排序。

各自的排序当中nuts和bolts的顺序是无关紧要的，只要他们一一匹配就可以。

/**
 * 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) {
        // write your code here
        if (nuts.size() != bolts.size()) {
            return;
        }
        int i = 0;
        int j = nuts.size() - 1;
        // call recursive function
        partitionNutsAndBolts(nuts, bolts, compare, i, j);
    }
    void partitionNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare, int start, int end) {
        if (start < end) {
            // use nuts to partition bolts
            int i = start;
            int j = end;
            while(i < j) {
                while(i < j && compare.cmp(nuts[start], bolts[i]) > 0) {
                    i++;
                }
                while(i < j && compare.cmp(nuts[start], bolts[j]) < 0) {
                    j--;
                }
                if (i < j) {
                    swap(bolts[i], bolts[j]);
                }
            }
            // update to the same pos as nuts and keep splitpos
            swap(bolts[start], bolts[i]);
            int splitpos = i;
            // use bolts to partition nuts
            i = start + 1;
            j = end;
            while(i < j) {
                while(i < j && compare.cmp(nuts[i], bolts[start]) < 0) {
                    i++;
                }
                while(i < j && compare.cmp(nuts[j], bolts[start]) > 0) {
                    j--;
                }
                if (i < j) {
                    swap(nuts[i], nuts[j]);
                }
            }
            // recursive
            partitionNutsAndBolts(nuts, bolts, compare, start + 1, splitpos);
            partitionNutsAndBolts(nuts, bolts, compare, splitpos + 1, end);
        } 
    }
};