2つの配列を比較するためのO（n）時間とO（n）空間のアルゴリズム

-2

Aの要素はO（N）時間とO A及びBはOで共通の要素（n）を持っているかどうかを確認する（n）の空間

2.Howに異なっている場合1.Howチェックします時間とO（n）の空間。

アルゴリズムでは、ハッシュセットやその他の高度なデータ構造を使用しないでください。 AとBは単純な配列です。

2017-01-22 Malgorythm

理論上、q1は要素の一意性問題と呼ばれ、O（nlogn）の下限を持つことが証明されています。しかし、数がn^2を超えないという条件があります。 – Malgorythm

配列がソートされていると、両方の操作が線形時間で簡単に実行できます。 n^2の境界は、線形時間基数ソート（radix n）を可能にする。

2017-01-22 03:45:11

配列はソートされているとはみなされません。その場合の解決策は何ですか？ – Malgorythm

@Malgorythm線形時間と空間を基数ソートでソートします。 –

だから、O（n）の時間と空間で最初に並べ替えます。その後、比較を使用します。しかし、比較はO（nlogn）を余分に取ることはありませんか？ – Malgorythm

ソート済みアレイをO（n）時間でマージのように比較できます。

しかし、O（n）で与えられた制限を使って配列をソートすることは可能ですか？はい、そうです。 Cormen et alアルゴリズムのコースは、基数/桁の並べ替えに専念する最後の章で、そのようなソート（n^2の範囲の整数配列）に関する割り当てを含んでいます。

質問は宿題のように見えるので、この手がかりは十分だと思います。

2017-01-22 03:46:03 MBo

これは宿題ではありません。私はより大きな問題を解決したい、そしてここで私はこの小さな部分にこだわりました。私は要素の範囲に制限があるので、O（n）の配列をソートするのに苦労しています。いくつかの洞察力を提供していただけますか？ – Malgorythm

@Malgorythm宿題がない場合は、ハッシュセットなどを使用してみませんか？ – melpomene

基数= nの基数ソートを考慮してください（数字は2桁以下です） – MBo

答えて