Posted on 2007-07-25 16:01
ZelluX 閱讀(396)
評論(0) 編輯 收藏 所屬分類:
Algorithm
問題：
有n個大小各不相同的螺帽及對應(yīng)的螺釘，要求在O(nlogn)的復(fù)雜度內(nèi)完成配對。螺釘之間、螺帽之間都無法直接比較大小，只能比較一顆螺帽與螺釘，判斷他們之間的大小差異。
感覺和快速排序的partition差不多。
首先任選一顆螺釘與各螺帽進(jìn)行比較，分成大小兩組，另外得到與改螺釘相匹配的螺帽。
然后用那個螺帽再和其他螺釘比較，也分成大小兩組，然后繼續(xù)二分遞歸。