3

n 個の整数の配列 A があります。k (k < n) 整数の配列 B もあります。必要なのは、配列 B に表示される配列 A の整数を 3 増やすことです。

最も明白な方法で行けば、n*k の複雑さになります。配列 A はソートできません (してはなりません)。

これを達成するためのより効率的な方法はありますか？

4

3 に答える 3

1

これを達成するためのより効率的な方法はありますか？

はい: の要素を に入れBますHashSet。ループしAて、現在の要素がセットに含まれている場合は、それを 3 増やします。これは O(n + k) の複雑さを持ちます。

例えば：

Set<Integer> bSet = new HashSet<>(B.length);

for (int a : B)  // O(k)
    bSet.add(a);

for (int i = 0; i < A.length; i++) {  // O(n)
    if (bSet.contains(a[i]))
        a[i] += 3;
}
于 2013-10-10T23:22:12.673 に答える
0

配列Bをソートできる場合-解決策は明らかです。ソートすると、「含む」をlog2（K）に最適化できるため、複雑さはN * log2（k）になります

配列Bをソートできない場合-唯一のことは簡単です N*K

アップデート

32ビット整数しかなく、十分なメモリがあることがわかっている場合、ビットマスクを本当に忘れていました-巨大なビットマスク配列を格納できます。「追加」と「含む」は常にO（1）になりますが、もちろん必要です非常に特別なパフォーマンスの最適化のみ

于 2013-10-10T23:27:49.137 に答える
0

整数が作成できる範囲内にあり、最大値の長さ (たとえば0 <= A[i] and B[i] <= 65535) で配列されている場合は、これを行うことができます

boolean [] constains = new boolean[65535];
for (int i = 0; i < k; i++){
    constains[B[i]] = true;
}

for (int i = 0; i < n; i++){
    if (constains[A[i]]){
        A[i] += 3;
    }
}

O（n + k）はどれですか

于 2013-10-10T23:55:12.683 に答える