Posted on 2007-07-25 16:01
ZelluX 阅读(384)
评论(0) 编辑 收藏 所属分类:
Algorithm
问题：
有n个大小各不相同的螺帽及对应的螺钉，要求在O(nlogn)的复杂度内完成配对。螺钉之间、螺帽之间都无法直接比较大小，只能比较一颗螺帽与螺钉，判断他们之间的大小差异。
感觉和快速排序的partition差不多。
首先任选一颗螺钉与各螺帽进行比较，分成大小两组，另外得到与改螺钉相匹配的螺帽。
然后用那个螺帽再和其他螺钉比较，也分成大小两组，然后继续二分递归。