使用分而治之的方法检测数组中的重复项

Question

我在考试时得到了以下问题,似乎可能无法实现.有什么我想念的吗？

给定n个对象的数组,只能进行相等性比较,并且对数组中的值范围一无所知,给出一个分而治之的解决方案,用于检测数组中是否存在任何重复项.这必须是O(nlogn)解决方案.

我们可以安全地假设由于问题的性质,解决方案可能与数据结构或基数排序无关,那么这可以就地完成吗？

如果是这样,怎么样？

Answer 1

O(nlogn)如果您无法订购商品,则无法检查重复项,如果只能比较相等,则无法订购.

事实上,你不能确定没有重复,除非你比较每一对,并有n(n-1)/2这样的对.