Nuts and Bolts Problem · 數據結構與算法/leetcode/lintcode題解

# Nuts and Bolts Problem ### Source - lintcode: [(399) Nuts & Bolts Problem](http://www.lintcode.com/en/problem/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. The order of the nuts or bolts does not matter. You just need to find the matching bolt for each nut. ~~~ ### 題解首先結合例子讀懂題意，本題為 nuts 和 bolts 的配對問題，但是需要根據題目所提供的比較函數，且 nuts 與 nuts 之間的元素無法直接比較，compare 僅能在 nuts 與 bolts 之間進行。首先我們考慮若沒有比較函數的限制，那么我們可以分別對 nuts 和 bolts 進行排序，由于是一一配對，故排完序后即完成配對。那么在只能通過比較對方元素得知相對大小時怎么完成排序呢？我們容易通過以一組元素作為參考進行遍歷獲得兩兩相等的元素，這樣一來在最壞情況下時間復雜度為 O(n2)O(n^2)O(n2), 相當于冒泡排序。根據排序算法理論可知基于比較的排序算法最好的時間復雜度為 O(nlogn)O(n \log n)O(nlogn), 也就是說這道題應該是可以進一步優化。回憶一些基于比較的排序算法，能達到 O(nlogn)O(n \log n)O(nlogn) 時間復雜度的有堆排、歸并排序和快速排序，由于這里只能通過比較得到相對大小的關系，故可以聯想到快速排序。快速排序的核心即為定基準，劃分區間。由于這里只能以對方的元素作為基準，故一趟劃分區間后僅能得到某一方基準元素排序后的位置，那通過引入 O(n)O(n)O(n) 的額外空間來對已處理的基準元素進行標記如何呢？這種方法實現起來較為困難，因為只能對一方的元素劃分區間，而對方的元素無法劃分區間進而導致遞歸無法正常進行。山窮水盡疑無路，柳暗花明又一村。由于只能通過對方進行比較，故需要相互配合進行 partition 操作(這個點確實難以想到)。核心在于：**首先使用 nuts 中的某一個元素作為基準對 bolts 進行 partition 操作，隨后將 bolts 中得到的基準元素作為基準對 nuts 進行 partition 操作。** ### Python ~~~ # class Comparator: # def cmp(self, a, 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: # @param nuts: a list of integers # @param bolts: a list of integers # @param compare: a instance of Comparator # @return: nothing def sortNutsAndBolts(self, nuts, bolts, compare): if nuts is None or bolts is None: return if len(nuts) != len(bolts): return self.qsort(nuts, bolts, 0, len(nuts) - 1, compare) def qsort(self, nuts, bolts, l, u, compare): if l >= u: return # find the partition index for nuts with bolts[l] part_inx = self.partition(nuts, bolts[l], l, u, compare) # partition bolts with nuts[part_inx] self.partition(bolts, nuts[part_inx], l, u, compare) # qsort recursively self.qsort(nuts, bolts, l, part_inx - 1, compare) self.qsort(nuts, bolts, part_inx + 1, u, compare) def partition(self, alist, pivot, l, u, compare): m = l i = l + 1 while i <= u: if compare.cmp(alist[i], pivot) == -1 or \ compare.cmp(pivot, alist[i]) == 1: m += 1 alist[i], alist[m] = alist[m], alist[i] i += 1 elif compare.cmp(alist[i], pivot) == 0 or \ compare.cmp(pivot, alist[i]) == 0: # swap nuts[l]/bolts[l] with pivot alist[i], alist[l] = alist[l], alist[i] else: i += 1 # move pivot to proper index alist[l], alist[m] = alist[m], alist[l] return m ~~~ ### C++ ~~~ /** * 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) { if (nuts.empty() || bolts.empty()) return; if (nuts.size() != bolts.size()) return; qsort(nuts, bolts, compare, 0, nuts.size() - 1); } private: void qsort(vector<string>& nuts, vector<string>& bolts, Comparator 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); } int partition(vector<string>& str, string& pivot, Comparator compare, int l, int u) { int m = l; for (int i = l + 1; i <= u; ++i) { if (compare.cmp(str[i], pivot) == -1 || compare.cmp(pivot, str[i]) == 1) { ++m; std::swap(str[m], str[i]); } else if (compare.cmp(str[i], pivot) == 0 || compare.cmp(pivot, str[i]) == 0) { // swap nuts[l]/bolts[l] with pivot std::swap(str[i], str[l]); --i; } } // move pivot to proper index std::swap(str[m], str[l]); return m; } }; ~~~ ### Java ~~~ /** * 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; 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) { // int m = l; for (int i = l + 1; i <= u; i++) { if (compare.cmp(str[i], pivot) == -1 || compare.cmp(pivot, str[i]) == 1) { // m++; swap(str, i, m); } else if (compare.cmp(str[i], pivot) == 0 || compare.cmp(pivot, str[i]) == 0) { // swap nuts[l]/bolts[l] with pivot swap(str, i, l); i--; } } // move pivot to proper index swap(str, m, l); return m; } private void swap(String[] str, int l, int r) { String temp = str[l]; str[l] = str[r]; str[r] = temp; } } ~~~ ### 源碼分析難以理解的可能在`partition`部分，不僅需要使用`compare.cmp(alist[i], pivot)`, 同時也需要使用`compare.cmp(pivot, alist[i])`, 否則答案有誤。第二個在于`alist[i] == pivot`時，需要首先將其和`alist[l]`交換，因為`i`是從`l+1`開始處理的，將`alist[l]`換過來后可繼續和 pivot 進行比較。在 while 循環退出后在將當前遍歷到的小于 pivot 的元素 alist[m] 和 alist[l] 交換，此時基準元素正確歸位。對這一塊不是很清楚的舉個例子就明白了。 ### 復雜度分析快排的思路，時間復雜度為 O(2nlogn)O(2n \log n)O(2nlogn), 使用了一些臨時變量，空間復雜度 O(1)O(1)O(1). ### Reference - [LintCode/Nuts & Bolts Problem.py at master · algorhythms/LintCode](https://github.com/algorhythms/LintCode/blob/master/Nuts%20%26%20Bolts%20Problem.py)