1

これは学校の課題ですが、プログラムを「最大のパフォーマンスで実装する」必要がありました。これは、メモリが速度を上回るかどうかなどがわからないため、私の好みにはあいまいです。しかし、私が探しているのは入力データに対してスマートな操作を行うことで問題を解決する「トリッキーな」方法があるかどうかです。

したがって、ここに問題があります。AとBの2つの配列があると考えて、Bにそのような整数がある場合に1を返す関数を記述します。これは、Aの後続の2つの要素の合計に等しくなります。

以下は私の記事です。Hashmap<Integer>スピードアップに必要なメモリは、O（n）ではなくO（n * m）の速度で動作するのに十分なほど強力な欠点であると考えたため、使用しなかったことに注意してください。

public static int arrayContainsSum(int[] a, int[] b)
{
    int offsetA = a.length - 1;
    int offsetB = offsetA;
    int index = b.length - 1;
    int result = 0;
    int tested;

    while (index >= 0)
    {
        if (offsetA > 0) a[offsetA] += a[--offsetA];
        else if (offsetA == 0) // This has a danger of overflowing the int
            a[offsetA--] = multiply(a);
        tested = b[index];
        if ((offsetA < 0 && tested != 0 && a[0] % tested != 0) ||
            offsetB == 0)
        {
            // No point to test this element as it doesn't 
            //divide the product of sums
            offsetB = a.length - 1;
            index--;
        }
        if (tested == a[offsetB--])
        {
            result = 1;
            break;
        }
    }
    return result;
}

private static int multiply(int[] input)
{
    int accumulator = input.length > 0 ? 1 : 0;
    for (int i : input)
        if (i != 0) accumulator *= i;
    return accumulator;
}

私が気にしないことがいくつかあります：整数のオーバーフロー（乗算の結果として発生する可能性があります）。array.lengthローカル変数からの読み取りと同じくらい速いと思いました。

しかし、繰り返しになりますが、私の質問はむしろ「この問題を分析的に解決することはできなかったのか」ということです。これはより良い効率を意味しますか？

PS。この問題では、配列に一意のメンバーのみが含まれているかどうかについては言及されていません。制限はありません。また、が最小の要素よりも小さいか、最大の要素よりも大きい場合に、いくつかのルックアップを節約できるように並べ替えるaことで、最適化（そのような場合を検出した場合）が可能になると思いますが、これも複雑さが増すという犠牲を払うことになりますが、完全に正当化されるわけではありません。b[x]aa

4

3 に答える 3

1 
public static int arrayContainsSum(int[] a, int[] b) {
  final Set<Integer> sums = new HashSet<Integer>();
  for (int i = 0; i < a.length - 1; i++) sums.add(a[i] + a[i+1]);
  for (int x : b) if (sums.contains(x)) return 1;
  return 0;
}
于 2012-04-28T21:40:42.100 に答える
0

疑わしい場合は、ブルートフォースを使用してください。

もちろん、タスクがパフォーマンスの高いソリューションを作成することである場合、それだけでは不十分かもしれませんが、ソリューションを最適化する前に、ソリューションが必要です。

val a = List (3, 9, 7, 4, 16)    
val b = List (29, 12, 21, 16, 18, 14) 

for (i <- (0 to a.length - 2); 
  j = i+1;
  if b.exists (_ == a(i)+a(j))) yield (a(i), a(j), a(i)+a(j))

どのくらいの頻度で実行されますか？外側のループは1からarray-length-1（ここにリストされています）まで実行され、iを生成します。jは後続の要素にすぎません。

ただし、bの場合、常にアレイ全体で実行されます。

bを値でソートすると、bでバイナリルックアップを実行できます。2つの配列が与えられているため、ルールからHashMapは許可されていないと思います。それ以外の場合、HashMapの方が高速です。

于 2012-04-28T21:47:32.723 に答える
0

100万を超える要素があり、1秒以上かかる場合を除いて、速度は重要ではありません。ところで、100万要素を超えるサイズの配列は作成したくありません。

7までのJavaバージョンに基本的なセット操作さえ含まれていないのは幸いではありません。ただし、それらはGoogle Guavaライブラリで見つけることができます（そのコードは適切にテストされており、可能な限り効率的です）。

20個の要素が2セットあり、1から100および200までランダムに選択されているとしますa。b

a = RandomInteger[{100}, 20]
b = RandomInteger[{200}, 20]

aその後、後続の要素の合計のセットのどの要素が交差するかを見つけたいと思いますb

ap = Table[Total[{a[[i]], a[[i + 1]]}], {i, 1, Length[a] - 1}]
Intersection[ap, b]

例えば：

{73,43,99,33,80,35,54,82,50,23,92,22,54,4,14,14,8,80,92,85}
{121,139,158,158,51,176,65,84,76,172,73,148,71,128,55,134,4,32,183,134}
{116,142,132,113,115,89,136,132,73,115,114,76,58,18,28,22,88,172,177}
{73,76,172}
于 2012-04-28T21:13:11.227 に答える