要素を持つ配列が与えられたx場合、合計すると 0 になる 4 つの数値を見つける必要があります。また、そのような合計がいくつ存在するかを判断する必要があります。
したがって、3 次時間には 3 つのネストされた反復子が含まれるため、最後の数値を検索するだけで済みます (二分探索を使用)。
代わりにデカルト積 (X と Y に同じ配列) を使用することで、すべてのペアとその合計を 2 次配列に格納できます。したがって、各合計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;
}
したがって、257 個ではなく 261 個の解を見つけることができました。これは問題があることを示している可能性がありdouble、実際には精度が失われています。ただし、261 は 528 から遠く離れていますが、原因を突き止めることができません。
最終編集: これは恐ろしく醜いコードだと思いますが、それでも機能しているようです。すでに 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;
}