Nuts and Bolts Problem
Question
- lintcode: (399) Nuts & Bolts Problem
1 | Given a set of n nuts of different sizes and n bolts of different sizes. |
题解
首先结合例子读懂题意,本题为 nuts 和 bolts 的配对问题,但是需要根据题目所提供的比较函数,且 nuts 与 nuts 之间的元素无法直接比较,compare 仅能在 nuts 与 bolts 之间进行。首先我们考虑若没有比较函数的限制,那么我们可以分别对 nuts 和 bolts 进行排序,由于是一一配对,故排完序后即完成配对。那么在只能通过比较对方元素得知相对大小时怎么完成排序呢?
我们容易通过以一组元素作为参考进行遍历获得两两相等的元素,这样一来在最坏情况下时间复杂度为 \[O(n^2)\], 相当于冒泡排序。根据排序算法理论可知基于比较的排序算法最好的时间复杂度为 \[O(n \log n)\], 也就是说这道题应该是可以进一步优化。回忆一些基于比较的排序算法,能达到 \[O(n \log n)\] 时间复杂度的有堆排、归并排序和快速排序,由于这里只能通过比较得到相对大小的关系,故可以联想到快速排序。
快速排序的核心即为定基准,划分区间。由于这里只能以对方的元素作为基准,故一趟划分区间后仅能得到某一方基准元素排序后的位置,那通过引入 \[O(n)\] 的额外空间来对已处理的基准元素进行标记如何呢?这种方法实现起来较为困难,因为只能对一方的元素划分区间,而对方的元素无法划分区间进而导致递归无法正常进行。
山穷水尽疑无路,柳暗花明又一村。由于只能通过对方进行比较,故需要相互配合进行 partition 操作(这个点确实难以想到)。核心在于:首先使用 nuts 中的某一个元素作为基准对 bolts 进行 partition 操作,随后将 bolts 中得到的基准元素作为基准对 nuts 进行 partition 操作。
Python
1 | # class Comparator: |
C++
1 | /** |
Java
1 | /** |
源码分析
难以理解的可能在partition
部分,不仅需要使用compare.cmp(alist[i], pivot)
, 同时也需要使用compare.cmp(pivot, alist[i])
, 否则答案有误。第二个在于alist[i] == pivot
时,需要首先将其和alist[l]
交换,因为i
是从l+1
开始处理的,将alist[l]
换过来后可继续和 pivot 进行比较。在 while 循环退出后在将当前遍历到的小于 pivot 的元素 alist[m] 和 alist[l] 交换,此时基准元素正确归位。对这一块不是很清楚的举个例子就明白了。
复杂度分析
快排的思路,时间复杂度为 \[O(2n \log n)\], 使用了一些临时变量,空间复杂度 \[O(1)\].
Reference
Nuts and Bolts Problem