4

各位置に 3 つの int 値 (x、y、z) を持つクラス オブジェクトが含まれる配列があります。別の配列から、すべての要素をソース配列にコピーする必要があります。配列要素ごとに、重複を避けるために x、y、z 値を確認する必要があります。o(n^2) よりも効率的に行うことは可能ですか?

4

2 に答える 2

6

2つの配列の元の順序を失ってもかまわない場合：

std::sort(first_array, first_array + N);
std::sort(second_array, second_array + M);
std::set_union(
    first_array, first_array+N, 
    second_array, second_array+M, 
    target_array
);

NおよびMは、配列内の要素の数です。operator<クラスを定義するか、特殊化する必要があります。あるいはstd::less、コンパレータ関数を記述して、とに提供しsortますset_union。

時間計算量は次O(N log N + M log M)のとおりです。これはsort遅い部分であり、set_union線形です。

自分自身の中に（それらの間だけでなく）重複がすでに含まれている場合first_array、またはすでに含まれている可能性がある場合second_arrayは、それらを削除するための追加の手順が必要です。これにより、順序だけでなく、ソース配列の重複も失われます。

std::sort(first_array, first_array + N);
MyClass *first_end = std::unique(first_array, first_array + N);
std::sort(second_array, second_array + M);
MyClass *second_end = std::unique(second_array, second_array + M);
std::set_union(
    first_array, first_end, 
    second_array, second_end, 
    target_array
);

set_unionまたは、1回のパスでマージおよび重複排除する変更バージョンを作成することもできます。

first_array[編集：申し訳ありませんが、これを書いているときに、結果が最終的に別のにではなく、に戻ることを見逃しましたtarget_array。set_union出力を入力の1つとして使用しないため、ターゲットアレイ用に追加のメモリが必要になります。もちろん、ソースが十分に大きい場合は、ターゲットアレイをソースアレイにコピーして戻すことができます。]

元の配列の順序を保持したい場合は、コンテナーを作成して、次のことを確認できます。

container<MyClass> items(first_array, first_array + N);
MyClass *dst = first_array + N;
for (MyClass *it = second_array; it != second_array + M; ++it) {
    if (items.count(*it) == 0) {
        items.insert(*it);
        *dst++ = *it;
    }
}

配列内に重複を含めることができる場合は、items空とdst = first_arrayで開始し、両方の入力配列をループします。

containerstd::set（この場合、時間は、O(N log N + M log(N + M))実際にはO(N log N + M log M)再び、次数コンパレータが必要です）、またはstd::unordered_setC ++ 11（この場合、予想される時間はO(N + M)病理学的な最悪の場合であり、特殊化する必要があります）std::hashまたはそれ以外の場合は、ハッシュ関数を記述し、次数コンパレータの代わりに等号関数も提供します）。C ++ 11より前は、他のハッシュコンテナが標準では利用できませんでした。

余分なメモリを気にせず、元の順序を失ってもかまわない場合：

container<MyClass> items(first_array, first_array + N);
items.insert(second_array, second_array + M);
std::copy(items.begin(), items.end(), first_array);

単に結果のためのスペースがあるのではなく、（多くの）余分なメモリを使用せず、ソース配列にM個の追加要素用のスペースがある場合：

std::copy(second_array, second_array + M, first_array + N);
std::sort(first_array, first_array + N + M);
MyClass *dst = std::unique(first_array, first_array + N + M);
// result now has (dst - first_array) elements
于 2012-10-10T09:29:22.423 に答える
3

x、y、zを使用してオブジェクトの比較を定義し、両方の配列（または必要に応じてコピー）を並べ替えてから、最初の要素からすべての要素をコピーし、2番目の要素から一致しない要素のみをコピーするセカンダリ宛先リストを作成します。必要に応じて、最初のアレイにコピーして戻します。

複雑さ：max（O（n log n）、O（m log m））、ソートが支配的であり、宛先リストの入力はO（max（n、m））にあるため。

これは、アルゴリズムが必ずしも効率的であるとは限りません。小さい配列の場合、コピーと並べ替えが主流になります。

于 2012-10-10T09:29:58.237 に答える