2

これは非常に些細なことかもしれませんが、n^2 時間未満で実行される答えを見つけるのに苦労しています。2 つの文字列配列があり、両方の配列に存在する文字列を知りたいとしましょう。VB.NETで効率的にそれを行うにはどうすればよいですか、または二重ループ以外にこれを行う方法はありますか?

4

4 に答える 4

3

簡単な方法 (.NET 3.5 がないと仮定) は、1 つの配列から文字列をハッシュテーブルにダンプし、ハッシュテーブルに対してチェックする他の配列をループ処理することです。これは、n^2 検索よりもはるかに高速です。

于 2009-03-23T16:27:54.570 に答える
3

両方の配列を並べ替えると、それぞれを 1 回ずつ調べて、一致するすべての文字列を見つけることができます。

擬似コード:

while(index1 < list1.Length && index2 < list2.Length)
{
   if(list1[index1] == list2[index2])
   {
      // You've found a match
      index1++;
      index2++;
   } else if(list1[index1] < list2[index2]) {
      index1++;
   } else {
      index2++;
   }
}

次に、並べ替えにかかる時間を短縮しました。

于 2009-03-23T16:29:52.897 に答える
2

両方のリストを並べ替えます。次に、リスト A の次のエントリが「cobble」で、リスト B の次のエントリが「確定」である場合、「cobble」はリスト B にないことを確実に知ることができます。リストにあるポインタ/カウンタを進めるだけです。下位の結果とランキングを上げます。

例えば：

リスト 1: D、B、M、A、I
リスト 2: I、A、P、N、D、G

並べ替え:

リスト 1: A、B、D、I、M
リスト 2: A、D、G、I、N、P

A vs A --> 一致、A を保存、
B vs D の両方を進める --> B D vs D --> 一致、D を保存、
I vs G の両方を進める --> I>G、2
I vs I を進める -->一致し、I を保存し、
M 対 N の両方を進めます --> M リスト 1 にはアイテムがありません。終了します。
一致するリストは A、D、I です

2 つのリストは O(n log(n)) を並べ替え、さらに O(n) の比較で O(n(log(n) + 1)) になります。

于 2009-03-23T16:29:21.120 に答える
2

配列の 1 つが並べ替えられている場合は、内側のループでバイナリ検索を実行できます。これにより、次の時間が短縮されます。O(n log n)

于 2009-03-23T16:29:44.427 に答える