输入是 200 K double 对，即 key 对。它们没有范围，即键可以是任何数字。
现在，任务是将这些大数据分为以下几类:
key1 => (value1, value2, value3)
key2 => (value1, value2, value3)
...
...
比较键的相等性( double )时，可以考虑使用 EPSILON(例如 1e-8)。
我开发了一个复杂度为 O(n^2) 的解决方案，但它对于 200K double 来说太慢了。想知道有什么改进吗？例如 O(nlogn) 会很好。
另一个例子，
Input: <0.1, 0.3>, <0.1, 0.4>, <0.2, 0.5>, <0.2, 0.6>, <0.3, 0.7>
Output
0.1 => (0.3, 0.4)
0.2 => (0.5, 0.6)
0.3 => (0.7)
最佳答案
为了避免分组键依赖于其他分组键的问题 - 处理键的问题
(1.0, 1.0 + EPSILON, 1.0 + 2xEPSILON, 1.0 + 3xEPSILON)
与键一致
(1.0, 1.0 + 2xEPSILON, 1.0 + 4xEPSILON, ...)
最合乎逻辑的选择似乎是使用 HashSet 并通过将键的实际 double 值量化到大小为 EPSILON 的桶中来创建哈希键。
根据您对 EPSILON 的要求，您可以采用下面的讨论将您的预期输入范围量化为类似 long 的内容:
关于algorithm - 对双对数组进行分组的最快方法是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23768579/