我最近在接受采访时被问到这个问题:
每个都有两个大小为'n'的数组.一个阵列有螺母,另一个有螺栓.每个螺母恰好适合一个螺栓,反之亦然.当您将螺母与螺栓进行比较时,您会得到3个结果中的一个:紧,松,合适.
你如何有效地找到独特的映射？
无法在任何一组上进行排序.你永远不知道b1是否小于b2或
n1是否小于n2.其中n1,n2是螺母,b1,b2是螺栓.你唯一能做的就是将螺母与螺栓进行比较并得到一个结果:紧,合适,松动.
uns*_*sym 13
类似快速排序的算法完成了这项工作:
n并用它作为枢轴将螺栓组B分成三组:紧(B1),松(B2),适合.b.现在您使用此螺栓作为枢轴将螺母组N\n分成两组:tight(N1)或松散(N2).N1和B1,n和b,N2和B2.所有这些都是相同的大小.您可以在(N1,B2)和(N2,B1)上递归地执行相同的分区,您可以得到最终答案.很明显,复杂性O(N log N)与快速排序相同.
| 归档时间： |
|
| 查看次数： |
768 次 |
| 最近记录： |