【Lintcode】399. Nuts & Bolts Problem

题目地址：

https://www.lintcode.com/problem/nuts-bolts-problem/description

给定两个字符串数组，第一个数组代表各个螺母（nuts）的名字，第二个数组代表各个螺丝（bolts）的名字。再给一个比较器，但是只能比较螺母和螺丝的大小，螺母之间或者螺丝之间都是不能比较的。要求对两个数组重新排序，使得对应位置的螺母和螺丝是匹配的。

思路是快速排序。开一个函数void quickSort(String[] nuts, String[] bolts, NBComparator compare, int l, int r)用来排序nuts和bolts的在区间$[l,r]$中的元素。步骤是这样的：
1、先按照nuts[l]为基准，去partitionbolts，使得bolts中比nuts[l]大的都归到一边，比nuts[l]小的都归到另一边，并得到partition后的分界点下标。这个下标p显然使得bolts[p]与nuts[l]相等。
2、再按照bolts[p]为基准，去partitionnuts，使得nuts中比bolts[p]大的都归到一边，比bolts[p]小的都归到另一边（注意，这里的比较大小要和上面步骤1的比较大小要统一。意思是，例如，如果上面是把比nuts[l]大的都归到右边，那么这里nuts中比bolts[p]大的也要都归到右边）。partition完毕之后，bolts[p]和nuts[p]就匹配了。
3、递归排序两个数组的$[l,p-1]$和$[p+1,r]$区间。

代码如下：

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
        // 特判
        if (nuts == null || bolts == null) {
            return;
        }
        if (nuts.length != bolts.length) {
            return;
        }
        
        // 开始排序
        quickSort(nuts, bolts, compare, 0, nuts.length - 1);
    }
    
    private void quickSort(String[] nuts, String[] bolts, NBComparator compare, int l, int r) {
        if (l >= r) {
            return;
        }
        
        // 通过nuts[l]将bolts的[l, r]区间做partition
        int part_idx = partition(bolts, nuts[l], compare, l, r);
        // 通过bolts[part_idx]将nuts的[l, r]区间做partition
        partition(nuts, bolts[part_idx], compare, l, r);
        // 递归partition左半边和右半边
        quickSort(nuts, bolts, compare, l, part_idx - 1);
        quickSort(nuts, bolts, compare, part_idx + 1, r);
    }
    
    // 通过pivot对str的[l, r]区间进行partition
    private int partition(String[] str, String pivot, NBComparator compare, int l, int r) {
    	// 先找到pivot对应的那个str中与之匹配的字符串的位置，将其换到区间左端点
        for (int i = l; i <= r; i++) {
            if (compare.cmp(pivot, str[i]) == 0 || compare.cmp(str[i], pivot) == 0) {
                String tmp = str[i];
                str[i] = str[l];
                str[l] = tmp;
                break;
            }
        }
        
        int i = l, j = r;
        // 缓存一下区间左端点，也就是最后partition分界点的那个字符串
        String s = str[l];
        // 以下循环是将比pivot大的都放到右边，小的都放到左边
        while (i < j) {
            while (i < j && (compare.cmp(str[j], pivot) == 1 || compare.cmp(pivot, str[j]) == -1)) {
                j--;
            }
            str[i] = str[j];
            while (i < j && (compare.cmp(str[i], pivot) == -1 || compare.cmp(pivot, str[i]) == 1)) {
                i++;
            }
            str[j] = str[i];
        }
        
        // 把分界点赋值回去
        str[i] = s;
        // 返回分界点
        return i;
    }
}

interface NBComparator {
    int cmp(String a, String b);
}

平均时间复杂度$O(n\log n)$，空间$O(\log n)$（递归栈深度）。关于快速排序的平均复杂度的证明，可以参考https://blog.csdn.net/qq_46105170/article/details/104085776。注意这里所写的复杂度是平均复杂度，并不是最坏复杂度，最坏复杂度是时间$O(n^2)$，空间$O(n)$，但期望而言不会遇到这么坏的情况。