4

2 つのリストでいくつかの共通項目を見つける必要があります。並べ替えはできません。順序が重要です。secondListから の要素がいくつ出現するかを調べなければなりませんfirstList。以下のようになります。

int[] firstList;
int[] secondList;
int iterator=0;
for(int i:firstList){
 while(i <= secondList[iterator]/* two conditions more */){
       iterator++;
       //some actions
   }
}

このアルゴリズムの複雑度はnxnです。この操作の複雑さを軽減しようとしていますが、要素をさまざまな方法で比較する方法がわかりません。何かアドバイス？

編集: 例:A=5,4,3,2,3 B=1,2,3 ペアを探しますB[i],A[j] 条件: when

B[i] < A[j]
         j++

いつ

B[i] >= A[j]
         return B[i],A[j-1]

Aのリストから要素j-1への次の反復(平均for(int z=0;z<j-1;z++)) よくわかりません。 重複は許可されます。

4

5 に答える 5

5

私のアプローチは、最初の配列のすべての要素を a に入れHashSet、2 番目の配列を反復処理することです。これにより、複雑さが 2 つの配列の長さの合計に軽減されます。追加のメモリを使用するという欠点がありますが、より多くのメモリを使用しない限り、ブルート フォース ソリューションを改善できるとは思いません。

編集：問題に関するさらなる論争を避けるために。最初の配列で重複を許可されていて、2 番目の配列の要素が最初の配列と何回一致するかを実際に気にする場合は、 を使用しますHashMultiSet。

于 2013-01-15T10:16:26.957 に答える
3
  • 最初のリストのすべてのアイテムをセットに入れる
  • 2 番目のリストの各項目について、セット内にあるかどうかをテストします。

nxn以内で解決！

編集してください:)

セットの代わりに、項目をキー、出現回数を値とするマップを使用できます。

次に、2 番目のリストの各項目について、それがマップに存在する場合は、最初のリスト (辞書エントリの値) の出現ごとにアクションを 1 回実行します。

于 2013-01-15T10:17:23.703 に答える
1 
import java.util.*; 

int[] firstList;
int[] secondList;
int iterator=0;   

HashSet hs = new HashSet(Arrays.asList(firstList));
HashSet result = new HashSet();

while(i <= secondList.length){
  if (hs.contains( secondList[iterator]))  
  {
    result.add(secondList[iterator]);
  }   
 iterator++;
 }

結果には、必要な共通要素が含まれます。アルゴリズムの複雑さ n

于 2013-01-15T10:27:56.577 に答える
1

順序が重要だからといって、どちらか (または両方) のリストを並べ替えることができないわけではありません。これは、何かを並べ替える前に、最初にコピーする必要があることを意味するだけです。もちろん、コピーには追加のメモリが必要で、並べ替えには追加の処理時間が必要です...それでも、O(n^2) よりも優れたすべてのソリューションには、追加のメモリと処理時間が必要になると思います (提案された HashSet ソリューションにも当てはまります - すべての値を追加します) HashSet に追加すると、追加のメモリと処理時間がかかります)。

両方のリストの並べ替えは O(n * log n) 時間で可能で、リストが並べ替えられると共通の要素を見つけるのは O(n) 時間で可能です。ネイティブの O(n^2) アプローチよりも高速になるかどうかは、リストのサイズによって異なります。最終的には、さまざまなアプローチをテストするだけで、どのアプローチが最も速いかを知ることができます (これらのテストでは、最終的なコードで期待される現実的なリスト サイズを使用する必要があります)。

Big-O 記法は、絶対速度について何かを伝える記法ではなく、相対速度について何かを伝えるだけです。. たとえば、要素の入力セットから値を計算する 2 つのアルゴリズムがあり、一方が O(1) で、もう一方が O(n) である場合、これは、O(1) ソリューションが常に高速であることを意味しません。これは Big-O 表記の大きな誤解です。これは、入力要素の数が 2 倍になった場合でも、O(1) ソリューションには約 O(n) ソリューションにかかる時間は同じです。前の倍の時間。したがって、入力要素の数を常に増やしていくと、O(1) の解が O(n) の解よりも速くなる点が必ずあるはずですが、非常に小さな要素のセットの場合、O( 1) ソリューションは、実際には O(n) ソリューションよりも遅い場合があります。

于 2013-01-15T10:38:54.840 に答える
0

OK、このソリューションは、1 つ目または 2 つ目の配列に重複がない場合に機能します。質問が教えてくれないので、確信が持てません。

まず、LinkedHashSet<Integer>最初の配列から a を作成HashSet<Integer>し、2 番目の配列から a を作成します。

次に、2 番目のセットに含まれる要素のみを最初のセットに保持します。

3 番目に、最初のセットを反復して続行します。

// A LinkedHashSet retains insertion order
Set<Integer> first = LinkedHashSet<Integer>(Arrays.asList(firstArray));
// A HashSet does not but we don't care
Set<Integer> second = new HashSet<Integer>(Arrays.asList(secondArray));

// Retain in first only what is in second
first.retainAll(second);

// Iterate

for (int i: first)
    doSomething();
于 2013-01-15T10:29:56.440 に答える