我在考试中得到了以下问题，似乎不可能。有什么我想念的吗？
给定一个包含 n 个对象的数组，该数组只能比较是否相等，并且对数组中值的范围一无所知，给出一个分而治之的解决方案来检测数组中是否存在任何重复项。这必须是 O(nlogn) 解决方案。
由于问题的性质，我们可以放心地假设该解决方案可能与数据结构或基数排序无关，那么这可以就地完成吗？
如果是这样，怎么做？
问问题
2910 次
6 回答
6
如果您无法订购商品，则无法检查重复O(nlogn)商品，如果您只能比较是否相等，则无法订购它们。
事实上，除非你比较每一对，否则你不能确定没有重复，并且有n(n-1)/2这样的对。
于 2012-04-12T17:12:19.000 回答
1
如何使用哈希集。将每个项目添加到集合中。然后检查尺寸。然而，这不是分而治之。
相等性比较的结果会告诉您被比较的两个对象中的哪一个“更大”吗？
如果您可以创建对象集的总排序，我认为您可以使用其中一种就地除法和 conq 排序算法，但添加一些额外的逻辑来检测重复。（将 <= 检查变成 < 和 == 检查）
于 2012-04-12T16:51:36.657 回答
0
由于它是 O(nlogn)，基本上你可以对数组进行排序并找到重复项。既然你想使用分而治之，我建议使用快速排序。
于 2012-04-12T17:13:34.647 回答
0
您可以在 NlogN 时间内做到这一点的唯一方法是“作弊”。
在 .NET 和 Java 中，接口的任何实现，例如 .NET 的 IEquatable，它只公开一个 Equals() 方法，也是一个基层对象。.NET 和 Java 中的对象具有散列函数（在 .NET 中是 GetHashCode()；在 Java 中是 hashCode()）。因此，无论接口限制您使用哪种方法，您始终可以访问将产生数值的散列函数。
这将允许您散列每个对象并比较散列的相对大小。这反过来又允许您按哈希对数组进行排序，然后以线性时间对其进行扫描以检测重复项。您可以就地执行此操作，或者您可以通过将每个项目插入到以哈希值为键的红黑树、哈希表或字典中来保持原始数组完整（所有这些都具有 logN 或更好的访问时间和 logN 或更好的插入次）。
如评论中所述，这些方法中的任何一种都可以并行化到多个线程，从而满足“分而治之”的要求；排序可以通过并行 MergeSort 完成，同时根据您在环境中可以访问的对象，您可以使用线程安全的“并发”集合，进而允许您将数组拆分为插入到集合中的子数组多个线程。如果您将分配给每个线程的子数组重叠一个元素，则扫描排序列表也可以并行化，从而防止重复对中的一项在一个子数组中，而另一个在下一个子数组中。
于 2012-04-12T18:02:36.447 回答
0
也许还有另一种考虑分析的方法？
同意，最坏的情况是 O(N^2)。但最好的情况是 O(1)。
纯粹看只有equal，并且值的范围是未知的，那么可以公平地说只有一种方法可以得到 N^2，那就是当所有的值都是不同的或不相等的时候？
同样，只有一种方法可以保证在 1 个测试中找到重复项，即所有值都相等。
有很多方法不可能在找到相同的对之前比较所有对象。如果有 N/2 对、N/3 三元组、N/4 个四元组、N/sqrt(N) 组 sqrt(N) 重复项等，在找到一对，即重复项之前必须比较多少？
我认为这就像“通过从具有未知数量的相同袜子组的袜子抽奖中选择一对袜子，一组中有两个或多个相同的袜子”。袜子抽奖的所有者通过购买未知数量的相同袜子来补充抽奖，并在袜子上有洞时将其扔掉。我们不知道袜子磨损的速度有多快，也不知道主人买袜子的速度有多快。
平均而言，我们不会期望比N^2 更好的性能吗？
于 2012-04-12T18:47:30.027 回答
-1
您可以使用修改后的快速排序来解决此问题。如果不是比较 > 你只是用相等运算符替换它。修改后的快速排序会将项目组合在一起。
那么你所要做的就是寻找条纹来寻找骗子。
看看这个例子。
于 2019-10-15T18:11:11.223 回答