高性能なint配列を比較する - C＃、配列、アルゴリズム、データ構造

私は大学での私の時代から、intの2つの並べ替えられていない配列を比較し、一致の数を見つける方法を覚えていませんか？ それぞれの値は独自の配列で一意であり、両方の配列は同じサイズです。

例えば

int[5] a1 = new []{1,2,4,5,0}
int[5] a2 = new []{2,4,11,-6,7}

int numOfMatches = FindMatchesInPerformanceOfNLogN(a1,a2);

誰も覚えていますか？

回答：

回答№1は2

1つの配列をソートする必要があります。n * log（n）で表す。ソートされた配列（log（n））に対してバイナリ検索を実行する、ソートされていない配列（n）のすべての項目です。どちらもソートされていない場合、n * log（n）で比較する方法はありません。

---

回答№2については2

配列の1つの内容をa HashMap、他の配列の中に要素が存在するかどうかを確認することができます。 HashMap。これはO（n）です。

---

回答№3の場合は1

これはどう：

1. 2つの配列を連結する
2. 結果をクイックソートする
3. 配列[1]から配列[array.length - 1]までステップスルーし、配列[i - 1]を配列[i - 1]

彼らが同じなら、あなたは重複しています。これもO（n * log（n））でなければならず、それぞれのチェックに対してバイナリ検索を必要としません。

---

回答№4の場合は0

あなたはLINQを使うことができます：

var a1 = new int[5] {1, 2, 4, 5, 0};
var a2 = new int[5] {2, 4, 11, -6, 7};
var matches = a1.Intersect(a2).Count();

私はあなたがまっすぐ進む道を探しているのか、あるいは最速/最善の方法を求めているのか分からない...

---

回答№5の場合は0

あなたは私が知っている2つの方法を持っています（ref： http://www2.cs.siu.edu/~mengxia/Courses%20PPT/220/carrano_ppt08.ppt）：

再帰的（擬似コード）

Algorithm to search a[first] through a[last] for desiredItem
if (there are no elements to search)
return false
else if (desiredItem equals a[first])
return true
else
return the result of searching a[first+1] through a[last]

効率

May be O(log n) though I have not tried it.

順次検索（擬似コード）

public boolean contains(Object anEntry)
{
boolean found = false;
for (int index = 0; !found && (index < length); index++) {
if (anEntry.equals(entry[index]))
found = true;
}
return found;
}

シーケンシャル検索の効率

Best case  O(1)
Locate desired item first
Worst case  O(n)
Must look at all the items
Average case O(n)
Must look at half the items
O(n/2) is still O(n)

ソートされていない限り、O（log n）検索アルゴリズムを認識していません。

---

答え№6の場合は0

私はそれが最速の方法であるかどうかわからないが、あなたができる

int[] a1 = new []{1,2,4,5,0};
int[] a2 = new []{2,4,11,-6,7};
var result = a1.Intersect(a2).Count();

Intersect（）がIEnumerableで動作するので、これをintに最適化された他の方法と比較する価値があります。

---

回答№7は0

この問題は並列化にも影響します。 n1スレッドを生成し、それぞれがa1の要素とa2のn2要素を比較し、合計値を持つようにします。恐らく遅くても面白いかもしれませんが、n1 * n2スレッドを生成して、すべての比較を同時に行い、その後減らします。最初のケースのP >> max（n1、n2）、2番目のケースのP >> n1 * n2の場合、最初のケースではO（n）、2番目のケースではO（log n）ですべてを実行できます。

---