Lintcode399 Nuts & Bolts Problem solution 题解
【题目描述】
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 操作。
【参考答案】
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
最新文章
- EventBus使用详解(二)——EventBus使用进阶
- C语言样式的文件操作函数
- 在Android Studio中用Gradle添加Robolectric
- virsh default启动失败原因分析及解决
- Eclipse下绿色安装插件Aptana、Swing
- [翻译]Orchard文档-命令行基架
- tensorflow安装调试总结(持续更新)
- Thirft框架快速入门
- CountDownLatch的实现原理
- 用DDK开发的9054驱动 .
- 谷歌chrome 插件(扩展)开发——进阶篇(c#本地程序和插件交互)下
- Unity项目开发过程中常见的问题,你遇到过吗?
- 根据sockfd获取TCP连接本地地址以及对端地址
- CDOJ 1960 构造哈密顿路径
- Centos6.8通过yum安装mysql5.7 centos7.5适用
- C#中redis订阅后程序不再继续执行
- V-rep学习笔记:机器人模型创建1—模型简化
- 原生js--兼容获取窗口滚动条位置和窗口大小的方法
- Linux下一个最简单的不依赖第三库的的C程序(1)
- React中ref的用法
热门文章
- xml解析之sax解析原理图和技术介绍
- BIP Requests Are Failing With Error ";OPP Error Oracle.apps.xdo.XDOException: Error Creating Lock Fil
- Cocos2D:塔防游戏制作之旅(八)
- 第三方ProgressHUD进度条 技术分享
- Uva - 810 - A Dicey Problem
- 实例说明Java中的null
- ffdshow 源代码分析 6: 对解码器的dll的封装(libavcodec)
- 【面试笔试算法】Problem 8: 然而沼跃鱼早就看穿了一切(hiho题库)
- Java-ServletInputStream
- Oracle Advanced Pricing White Papers