Description

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. The order of the nuts or bolts does not matter. You just need to find the matching bolt for each nut.

Solution

1. 先在bolts中任意找一点作为nuts的nuts-pivot去partition nuts，返回nuts中和nuts-pivot对应的点的坐标index
2. 将nuts[nuts-pivot]作为bolts的bolts-pivot再去partition bolts
3. 此时的nuts和bolts都以index为界partition好了
4. 再重复1,2两个步骤去分别partition index前的部分和index后的部分

这里的partition函数，因为pivot已经提前给出了，所以先遍历数组，找到和pivot相对应的值，和left上的值swap，这样就又转化成了经典的以left上的点为pivot的partition方法，就又可以用模板啦

注意compare函数对a，b的类型有限定，因此compare.cmp(strs[left], pivot) == -1 || compare.cmp(pivot, strs[left]) == 1)这样两头都试试

/**
 * 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) {
        // write your code here
        sortNutsAndBoltsHelper(nuts, bolts, 0, nuts.length - 1, compare);
    }

    private void sortNutsAndBoltsHelper(String[] nuts, String[] bolts, int left, int right, NBComparator compare) {
        if (left >= right) {
            return;
        }
        int index = partition(nuts, left, right, bolts[left], compare);
        partition(bolts, left, right, nuts[index], compare);

        sortNutsAndBoltsHelper(nuts, bolts, left, index-1, compare);
        sortNutsAndBoltsHelper(nuts, bolts, index+1, right, compare);
    }

    private int partition(String[] strs, int left, int right, String pivot, NBComparator compare) {
        // find pivor, swap it to left
        for (int i = left; i <= right; i++) {
            if (compare.cmp(strs[i], pivot) == 0) {
                swap(strs, left, i);
                break;
            }
        }
        String now = strs[left];
        // normal partition process
        while (left < right) {
            while (left < right && (compare.cmp(strs[right], pivot) == 1 || 
            compare.cmp(pivot, strs[right]) == -1)) {
                right--;
            }
            strs[left] = strs[right];
            while (left < right && (compare.cmp(strs[left], pivot) == -1 || 
            compare.cmp(pivot, strs[left]) == 1)) {
                left++;
            }
            strs[right] = strs[left];
        } 

        strs[left] = now;

        return left;
    }

    private void swap(String[] strs, int left, int right) {
        String temp = strs[left];
        strs[left] = strs[right];
        strs[right] = temp;
    }
};