2

2 つの配列があるとします。

int[] a1 = {5,2,1,13,4,9,7};
int[] a2 = {3,1,6,9,23,12,34};

ここで、どちらの配列にも含まれていない値を取得したいと考えています。たとえば、8,10,11,14,...

私の現在の解決策は、可能な各値（約14000）の状態（使用/未使用）を追加のブール配列に保存することです。値を使用するとすぐに、追加の配列でマークされます。したがって、他の配列に含まれていない値を見つけたい場合は、追加の配列を調べて、マークされていない値を探すだけです。

これを行う別の（効率的な）方法はありますか？

4

6 に答える 6

0

この方法は、CPU で最も効率的であり、メモリを使用しません。初期データを変更する必要があり、 Google Guavaライブラリに基づいています。

配列を変更できない場合は、それらを複製できますa1.clone()。それでも非常に効率的です。

方法：

  • 両方の配列を並べ替える
  • Iterators.html#mergeSortedを使用して、マージされた並べ替え済みの数値セットを反復処理します。

コード：

Arrays.sort(a1);
Arrays.sort(a2);

Iterator<Integer> mergedIterator = Iterators.mergeSorted(Ints.asList(a1).iterator(), Ints.asList(a2).iterator());

... iterate to find gaps in the sorted sequence ...

時間の複雑さはO(n log(n))であり、メモリ消費はゼロ (一定) です。Trove4j ライブラリのように、反復子がボックス化操作を行わない場合は、より高速になる可能性があります。

于 2013-09-29T09:29:53.787 に答える