Lintcode399 Nuts & Bolts Problem solution 题解
发布在刷题能手——Lintcode 题解2018年4月10日view:1207
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

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 个不同大小的 nuts 和 n 个不同大小的 bolts。nuts 和 bolts 一一匹配。 不允许将 nut 之间互相比较,也不允许将 bolt 之间互相比较。也就是说,只许将 nut 与 bolt 进行比较, 或将 bolt 与 nut 进行比较。请比较 nut 与 bolt 的大小。

【题目链接】

www.lintcode.com/en/problem/nuts-bolts-problem/

【题目解析】

螺帽螺母问题脱胎于排序问题,这里的特别之处在于需要通过两个array进行对应的排序。这就需要利用一个array中的元素对另一个array进行partition,并反过来重复这一个过程,最终让两个array都满足comparator所定义的相同顺序。

这里要注意的是partition的变式,因为pivot并非来源当前array,只能通过一方元素作为基准,对另一个array进行partition。

核心在于:首先使用 nuts 中的某一个元素作为基准对 bolts 进行 partition 操作,随后将 bolts 中得到的基准元素作为基准对 nuts 进行 partition 操作。

【参考答案】

www.jiuzhang.com/solutions/nuts-bolts-problem/

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏