4μm实现的二次时间

Question

给定一个包含x元素的数组，我必须找到四个相加后等于零的数字。我还需要确定有多少这样的金额。

所以三次时间涉及三个嵌套迭代器，所以我们只需要查找最后一个数字(使用二进制搜索)。

相反，通过使用笛卡尔乘积(X和Y使用相同的数组)，我们可以将所有对及其和存储在辅助数组中。所以对于每个和d，我们只需要寻找-d。

对于(接近)二次时间，这应该是类似的：

public static int quad(Double[] S) {
ArrayList<Double> pairs = new ArrayList<>(S.length * S.length);
int count = 0;
for (Double d : S) {
for (Double di : S) {
pairs.add(d + di);
}
}
Collections.sort(pairs);
for (Double d : pairs) {
int index = Collections.binarySearch(pairs, -d);
if (index > 0) count++; // -d was found so increment
}
return count;
}

x是353(对于我们的特定数组输入)，解决方案应该是528，但使用此解决方案我只找到257。对于我们的立方时间，我们能够找到所有528个4sums

public static int count(Double[] a) {
Arrays.sort(a);
int N = a.length;
int count = 0;
for(int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
int l = Arrays.binarySearch(a, -(a[i] + a[j] + a[k]));
if (l > 0) count++;
}
}
}
return count;
}

替身的精度有可能丢失吗？

编辑：讨论过使用BigDecimal而不是double，但我们担心这会对性能产生影响。我们只处理数组中的353个元素，所以这对我们来说有什么意义吗？

编辑：如果我使用BigDecimal错误，我深表歉意。我以前从未和图书馆打过交道。因此，在多次建议后，我尝试使用BigDecimal代替

public static int quad(Double[] S) {
ArrayList<BigDecimal> pairs = new ArrayList<>(S.length * S.length);
int count = 0;
for (Double d : S) {
for (Double di : S) {
pairs.add(new BigDecimal(d + di));
}
}
Collections.sort(pairs);
for (BigDecimal d : pairs) {
int index = Collections.binarySearch(pairs, d.negate());
if (index >= 0) count++;
}
return count;
}

因此，它能够找到261个解决方案，而不是257个。这可能表明存在问题double，而我实际上正在失去精度。然而，261与528相距甚远，但我无法找到原因。

LASTEDIT：所以我相信这是一个可怕而丑陋的代码，但它似乎仍然有效。我们已经尝试了一段时间，但使用BigDecimal，我们现在可以获得全部528个匹配项。

我不确定它是否足够接近二次时间，时间会证明一切
我给你一个怪物：

public static int quad(Double[] S) {
ArrayList<BigDecimal> pairs = new ArrayList<>(S.length * S.length);
int count = 0;
for (Double d : S) {
for (Double di : S) {
pairs.add(new BigDecimal(d + di));
}
}
Collections.sort(pairs);
for (BigDecimal d : pairs) {
BigDecimal negation = d.negate();
int index = Collections.binarySearch(pairs, negation);
while (index >= 0 && negation.equals(pairs.get(index))) {
index--;
}
index++;
while (index >= 0 && negation.equals(pairs.get(index))) {
count++;
index++;
}
}
return count;
}

Answer 1

这里应该使用BigDecimal类而不是double，因为数组中浮点数字加起来的精确精度为0是解决方案所必需的。如果你的一个十进制值是.1，你就有麻烦了。该二进制分数不能用double精确地表示。以以下代码为例：

double counter = 0.0;
while (counter != 1.0)
{
System.out.println("Counter = " + counter);
counter = counter + 0.1;
}

您可能期望它执行10次，但这是一个无限循环，因为计数器永远不会精确到1.0。

示例输出：

Counter = 0.0
Counter = 0.1
Counter = 0.2
Counter = 0.30000000000000004
Counter = 0.4
Counter = 0.5
Counter = 0.6
Counter = 0.7
Counter = 0.7999999999999999
Counter = 0.8999999999999999
Counter = 0.9999999999999999
Counter = 1.0999999999999999
Counter = 1.2
Counter = 1.3
Counter = 1.4000000000000001
Counter = 1.5000000000000002
Counter = 1.6000000000000003

Answer 2

当您搜索对或单个元素时，需要使用多重性进行计数。也就是说，如果你在单态或对的数组中找到元素-d，那么你需要将计数增加找到的匹配数，而不仅仅是增加1。这可能就是为什么当你搜索配对时没有得到完整的结果。这可能意味着，当你在单身汉身上搜索时，匹配数528并不是真正的整数。一般来说，您不应该使用双精度算术来进行精确算术；请改用任意精度的有理数包。