【題目描述】
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.
給定一組 n 個(gè)不同大小的 nuts 和 n 個(gè)不同大小的 bolts峭咒。nuts 和 bolts 一一匹配黑滴。 不允許將 nut 之間互相比較，也不允許將 bolt 之間互相比較蜡吧。也就是說(shuō)纵穿，只許將 nut 與 bolt 進(jìn)行比較仅乓， 或?qū)?bolt 與 nut 進(jìn)行比較淳衙。請(qǐng)比較 nut 與 bolt 的大小鳖敷。
【題目鏈接】
www.lintcode.com/en/problem/nuts-bolts-problem/
【題目解析】
螺帽螺母問(wèn)題脫胎于排序問(wèn)題脖苏，這里的特別之處在于需要通過(guò)兩個(gè)array進(jìn)行對(duì)應(yīng)的排序。這就需要利用一個(gè)array中的元素對(duì)另一個(gè)array進(jìn)行partition定踱，并反過(guò)來(lái)重復(fù)這一個(gè)過(guò)程棍潘，最終讓兩個(gè)array都滿足comparator所定義的相同順序。
這里要注意的是partition的變式崖媚，因?yàn)閜ivot并非來(lái)源當(dāng)前array亦歉，只能通過(guò)一方元素作為基準(zhǔn)，對(duì)另一個(gè)array進(jìn)行partition畅哑。
核心在于：首先使用 nuts 中的某一個(gè)元素作為基準(zhǔn)對(duì) bolts 進(jìn)行 partition 操作肴楷，隨后將 bolts 中得到的基準(zhǔn)元素作為基準(zhǔn)對(duì) nuts 進(jìn)行 partition 操作。
【參考答案】
