出現回数が偶数の 1 つの数値を除いて、各数値の出現回数が奇数である配列が与えられます。偶数の出現数を見つけます。
例えば
1, 1, 2, 3, 1, 2, 5, 3, 3
出力は次のようになります。
2
制約事項は次のとおりです。
上記の制約により、比較ベースのソート、カウントソート、BST、ハッシュ、ブルートフォースなど、私の考えはすべて失敗しました。
知りたいのですが、XORing はここで機能しますか? はいの場合、どのように？
この問題は、数日間私の地下鉄の乗り物を占めています。ここに私の考えがあります。
A.ウェッブが正しく、この問題がインタビューに由来するか、ある種の学術的な問題である場合、私たちが行っている（間違った）仮定について考え、いくつかの単純なケースを検討してみてください.
頭に浮かぶ2つの極端なサブ問題は次のとおりです。
おそらく、異なる値の数の複雑さによってケースを分割する必要があります。
異なる値の数が O(1)であると仮定すると、各配列はから独立してm異なる値を持つことになります。この場合、元の配列をループして、各値の出現を消去およびカウントできます。例では、それは与えるだろうmn
1, 1, 2, 3, 1, 2, 5, 3, 3 -> First value is 1 so count and erase all 1
2, 3, 2, 5, 3, 3 -> Second value is 2, count and erase
-> Stop because 2 was found an even number of times.
これは、 の複雑さを持つ最初の極端な例を解決し、これはO(mn)に評価されO(n)ます。
より良い: 異なる値の数が である場合O(1)、ハッシュ マップ内の値の出現をカウントし、配列全体を読み取った後にそれらを調べ、偶数回出現するものを返すことができます。これはまだO(1)メモリと見なされます。
2 番目の極端なケースは、配列内で繰り返される値のみを見つけることです。これは では不可能に思えO(n)ますが、可能な特殊なケースがあります: 配列にn要素があり、内部の値が+ 繰り返される値 (またはx と y の間のすべての数値の{1, n-1}ようなバリアント) である場合。この場合、すべての値を合計し、合計から減算して、繰り返される値を取得します。n(n-1)/2
配列内のランダムな値を持つ 2 番目の極端なケース、または がm一定でない一般的なケースnを一定のメモリとO(n)時間で解決することは、私には不可能に思えます。
追加の注意:ここでは、必要な数が偶数回出現し、他の数が奇数回出現するため、XOR は機能しません。問題が「奇数回出現する数字を指定し、他のすべての数字は偶数回出現する」ことである場合、すべての値を XOR し、最後に奇数を見つけることができます。
このロジックを使用してメソッドを探すことができます。ある数値に奇数回適用すると 0 になり、偶数回適用すると ID になる関数のようなものが必要になります。これが可能だとは思わないでください。
序章
これが可能な解決策です。それはかなり不自然で実用的ではありませんが、問題もそうです。分析に穴があればコメントをいただければ幸いです。これが「公式」ソリューションの宿題や課題の問題である場合は、質問されてから1か月以上経過していることを考えると、元のポスターがまだ残っているかどうかも確認したいと思います。
まず、問題の詳細が特定されていないことをいくつか具体化する必要があります。必要な時間計算量はですがO(N)、何Nですか？ほとんどのコメンテーターNは、配列内の要素の数を想定しているようです。配列内の数値が固定の最大サイズである場合、これは問題ありません。その場合、基数ソートのMichaelGのソリューションで問題が解決されます。しかし、私は制約＃1を、元の投稿者による明確化がない限り、最大桁数を固定する必要はないと言っていると解釈します。したがって、n（小文字）が配列内の要素の数であり、要素mの平均の長さである場合、競合する入力の合計サイズはですmn。解決時間の下限は次のとおりです。O(mn)これは、ソリューションを検証するために必要な入力の読み取り時間であるためです。したがって、合計入力サイズに関して線形であるソリューションが必要ですN = nm。
たとえば、平均的な長さの要素でn = mあるがあります。比較ソートには操作が必要ですが、操作自体には平均して時間がかかるため、これは勝利ではありません。sqrt(N)sqrt(N)O( log(N) sqrt(N) ) < O(N)O(m) = O(sqrt(N))O( N log(N) )
また、基数ソートは、平均の長さではなく最大O(mn) = O(N)の長さである場合mに使用されます。数値が一定の範囲内にあると仮定した場合、最大長と平均長は同じオーダーになりますが、そうでない場合は、桁数が大きく可変の場合はパーセンテージが小さく、桁数が少ない場合はパーセンテージが大きくなる可能性があります。 。たとえば、数値の10％が長さで、90％が長さである可能性があります。平均の長さはですが、最大の長さなので、基数ソートはになります。m^1.1m*(1-10%*m^0.1)/90%mm^1.1O(m^1.1 n) > O(N)
問題の定義を大幅に変更したという懸念がないように、私の目標は、要素の数に比例する時間計算量を持つアルゴリズムを記述することですO(n)。ただし、各要素の長さに対して線形時間計算量の操作を実行する必要もあります。これにより、すべての要素の平均でこれらの操作はになりますO(m)。これらの演算は、要素のハッシュ関数と比較を計算するために必要な乗算と加算になります。そして、実際にこのソリューションがの問題を解決する場合O(N) = O(nm)、答えを検証するのに同じ時間がかかるため、これは最適な複雑さであるはずです。
問題の定義から省略されているもう1つの詳細は、データの処理中にデータを破棄できるかどうかです。わかりやすくするためにそうしますが、細心の注意を払えば回避できると思います。
考えられる解決策
まず、負の数が存在する可能性があるという制約は空です。データを1回通過するだけで、最小要素z数と要素数を記録しnます。2回目のパスでは、(3-z)各要素に追加するため、最小の要素は3になります（結果として一定数の数値がオーバーフローする可能性があるため、最初にデータを一定数追加パスしてテストする必要があります）これらはソリューション用です。）ソリューションができたら、単に減算(3-z)して元の形式に戻します。これで、それ自体は要素ではない3つの特別なマーカー値、、、およびが使用可能0に1なりました。2
ステップ1
中央値の中央値選択アルゴリズムを使用してp、配列の90パーセンタイル要素を決定しA、配列を2つのセットのセットに分割しますS。Tここで、Sは10% of nより大きい要素pをT持ち、はより小さい要素を持ちpます。これにはO(n)、ステップ（合計O(m)で平均してステップがかかる）時間がかかります。O(N)一致する要素は、またはのpいずれかに配置できますが、簡単にするために、配列を1回実行し、テストして、。に置き換えて削除します。セットは元々インデックスにまたがっており、ここで、は約であり、セットSTp0S0..ss10%nTインデックスの残りの90％にまたがりますs+1..n。
ステップ2
次に、ループしてi in 0..s、要素ごとにハッシュ関数をe_i計算します。一様分布を得るためにユニバーサルハッシュを使用します。したがって、ハッシュ関数は乗算と加算を実行し、各要素の長さに関して線形時間を要します。h(e_i)s+1..n
衝突には、修正された線形プロービング戦略を使用します。
h(e_i)のメンバーによって占有されているT（つまり、マーカーまたはA[ h(e_i) ] < pではありません）またはです。これはハッシュテーブルのミスです。スロットとから要素を交換して挿入します。120e_iih(e_i)
h(e_i)S （を意味するA[ h(e_i) ] > p）またはマーカー1またはのメンバーによって占められてい2ます。これはハッシュテーブルの衝突です。またはの重複またはe_iメンバーに遭遇するまで、線形プロービングを実行します。T0
のメンバーの場合T、これもハッシュテーブルの欠落であるため、スロットにスワップしてのようe_iに挿入します。(1.)i
の重複の場合e_i、これはハッシュテーブルヒットです。次の要素を調べます。その要素が1またはである場合は、すでに何度も2見てきましたが、 sをsに変更し、その逆を行って、パリティの変更を追跡します。次の要素がまたはでない場合は、前に1回しか見たことがありません。次の要素にを格納して、偶数回見たことを示します。次の「空の」スロットを探します。これは、スロットまたは0に移動するメンバーによって占有されているスロットであり、要素を上にシフトしてインデックスを下に移動し、次にパリティ情報を格納するためのスペースを確保します。 。保存する必要がないことに注意してくださいe_i1212e_i2e_iTih(e_i)+1h(e_i)e_i再びそれ自体なので、余分なスペースを使い果たしていません。
つまり、基本的に、ハッシュしたい要素の9倍のスロット数を持つ機能的なハッシュテーブルがあります。ヒットを取得し始めると、パリティ情報の保存も開始するため、スロット数が4.5倍になり、負荷率が非常に低くなる可能性があります。ここで機能する可能性のある衝突戦略はいくつかありますが、負荷率が低いため、衝突の平均数も少なく、線形プロービングは平均して適切な時間計算量でそれらを解決する必要があります。
ステップ3
0..sintoの要素のハッシュが終了したらs+1..n、をトラバースしs+1..nます。Sの要素の後にaが続く場合2、それが目標要素であり、完了です。の要素eのS後に別のS指示要素が続く場合は、e一度だけ検出され、ゼロにすることができます。同様に、奇数回見たeという意味が続き、とマーカーをゼロにすることができます。1ee1
必要に応じてすすぎ、繰り返します
目標要素が見つからない場合は、プロセスを繰り返します。90パーセンタイルパーティションは、n残りの最大要素の10％を最初に移動Aし、残りの要素（空の0マーカースロットを含む）を最後に移動します。以前と同じようにハッシュを続行します。毎回10％を処理するため、これを最大10回実行する必要がありますn。
結論分析
中央値の中央値アルゴリズムを介したパーティショニングの時間計算量はO(N)、10回ですが、それでもO(N)です。O(1)ハッシュテーブルの負荷が低く、合計O(n)でハッシュ操作が実行されるため、各ハッシュ操作は平均して実行されます（10回の繰り返しごとにnの約10％）。各要素には、それらに対して計算されたハッシュ関数があり、時間計算量はそれらの長さに線形であるため、平均してすべての要素にわたってです。したがって、集約されたハッシュ操作はです。したがって、これを適切に分析した場合、全体としてこのアルゴリズムはです。（これは、加算、乗算、比較、およびスワッピングの演算が入力に対して一定時間であると想定される場合も同様です。）nO(m)O(mn) = O(N)O(N)+O(N)=O(N)O(n)
このアルゴリズムは、1つの要素のみが偶数回発生するという問題定義の特殊な性質を利用していないことに注意してください。問題定義のこの特別な性質を利用しなかったということは、より良い（より賢い）アルゴリズムが存在する可能性を残しますが、最終的にはO（N）でなければなりません。
次の記事を参照してください。時間O（n）で実行され、インプレースでソートされるソートアルゴリズム。最大桁数が一定であると仮定すると、配列をO（n）時間でインプレースでソートできます。
その後、各数字の出現を数えるのが問題であり、出現回数が偶数である1つの数字を見つけるのに平均n/2の時間がかかります。