4

给定一个包含元素的数组x，我必须找到四个相加后等于 0 的数字。我还需要确定存在多少这样的总和。

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

相反，通过使用笛卡尔积（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 个 4 和

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;
}

是否有任何机会丢失了double的精度？

编辑：讨论了使用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：所以我相信这是可怕而丑陋的代码，但它似乎仍然有效。我们已经尝试过 while 但使用 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;
}
4

2 回答 2

1

您应该使用BigDecimal该类而不是double此处，因为数组中浮点数的精确精度加起来为 0 是您的解决方案所必需的。如果您的十进制值之一是 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
于 2014-02-27T20:30:23.267 回答
1

当您搜索对或单个元素时，您需要计算多重性。即，如果您在单例或成对数组中找到元素 -d，那么您需要将计数增加找到的匹配数，而不仅仅是增加 1。这可能是您没有得到完整的原因搜索对时的结果数。这可能意味着当您搜索单例时，匹配的数字 528 不是真正的完整数字。通常，您不应该将双精度算术用于精确算术；改用任意精度的有理数包。

于 2014-02-27T20:38:32.327 回答