数字が与えられ、それらの間で少なくとも 1 つの数字が共通するようなペアnの数を見つける必要があります。
例えば。5 つの数字の場合:
2837 2818 654 35 931
答え : 6
ここのペアは(2837,2818), (2837,35), (2837,931), (2818,931), (654,35), (35,931)
私の試み: 数値を 10 進数で格納し、数値を配列の桁数の形式で格納し、その数値の桁数を格納する構造を取りました。
ここで、各番号について、インデックス0〜9を含む配列でその番号をハッシュし、その後のすべての番号でそれらの数字のいずれかがすでに存在するかどうかをチェックしました。
私の試みはO(n^2)遅いです。より高速に動作する別のアルゴリズムはありますか?
ここで、何が変数で、何が定数であるかを理解することが重要です。
桁数は定数 (10) です。すべての桁数 (1024) も同様です。そのようなセットのすべてのペアの数も同様です (2 20または約 100 万)。それを活かしましょう。
入力を前処理して、サイズが一定の (入力サイズに依存しない) データ構造の「同等の」表現に変換してみましょう。次に、その一定サイズの構造で行うことは、定義上、一定時間の操作であるため、合計実行時間は、前処理フェーズのみによって漸近的に決定されます。
データ構造
1024 個の整数の配列を作成します。各バケット (インデックス) は一連の数字に対応します。各バケットに正確にその桁のセットを持つ入力番号の数を格納したいと考えています。
たとえば、3606 には数字 0、3、および 6 があるため、バケット 2 0 + 2 3 + 2 6 = 73 でカウントされます。
アルゴリズム
前処理は明らかです。次の数字 ( など) を取り、'3'その値 ( など) に変換し3、対応するビット ( など1 << 3) を計算し、それを (暫定的な) バケット インデックス変数に OR します。異なる数字は異なるビットに存在するため、すべての数字の組み合わせが一意のバケットを取得しますが、数字の繰り返しは削除されました。数値区切り記号に遭遇するまで、このようにループします。その時点で、バケット インデックスは最終的なものであり、バケットをインクリメントし、バケット インデックスをリセットして、次の桁までスキップすることができます。
それでおしまい。あとは羊を数えるだけです。おっとっと。羊のペア。
各バケットを他の各バケットと比較します (ただし、それ自体は比較しません)。2 つのインデックスが数字を共有している場合 (これは演算子を使用して決定できます&)、これら 2 つのバケットの内容を乗算し、その積をグローバルに維持された合計に加算します。
各バケットをそれ自体とも比較し、バケットの内容でx * (x - 1) / 2あるグローバルに維持された合計にのみ追加xします。
その合計があなたの結果です。
パフォーマンス
最悪の場合:O(n)はn入力サイズです。
定数要因も有利です。桁または区切りごとにいくつかの命令 (および RAM アクセス) が必要でした。一定のフェーズでは、100 万個のバケット ペアを調べ、各ペアに別の一握りの命令のようなものを費やします (RAM アクセスは不要で、データ構造は非常にコンパクトです)。これは超高速です。
理論家は、これは不正行為だと言うでしょう。入力の長さに上限はないと仮定しています (または、漸近的な複雑さについてまったく話すことができませんでした)。さらに、入力の長さの合計まで整数変数に入れることができると仮定しています。しかたがない。
より実践的なプログラマーは、アルゴリズムがアルファベット サイズで指数関数的であることに気付くでしょう。私たちは幸運でした。私たちの単語が数字ではなく、区切り記号を除いて任意の文字で構成されていた場合、私たちのアルゴリズムは依然として漸近的に線形時間アルゴリズムですが、メガバイトまで簡単に処理できる単純なアルゴリズムと比較して、どのような入力に対しても使用できないほど遅くなります。一度に入力します。
数字ごとに 1 つのセットの配列を作成します。
数字を繰り返し、含まれる数字の各セットに各数字を入れます。
10 セットすべてを反復し、セットのすべての要素を同じセット内の他のすべての要素と結合します。(または、結果に (a,b) と (b,a) が必要ない場合は、それ自体より大きい他のすべての要素。
これはまだ O(n^2) だと思いますが、フォーク結合アプローチを使用してうまく麻痺させることができます。
アップデート
結果の数だけが必要であることに気付きました。つまり、すべてのセットの size * size-1 の合計になります。セットへの挿入とそのサイズの取得は線形である必要があるため (私は思う)、これは実際には O(n) である可能性があります
別の更新
数値が明確で、ペアの数だけに関心がある場合は、セットは必要なく、代わりにカウンターが必要です。
コメント から：
Consider 1st pair in above questions test case (2837,2818), this will put first number in set containing digit 2 and 8 and same for 2818 now they are to be counted as one but counting in 2 and 8 will count it twice. I hope you understand what I am trying to say...
したがって、このアプローチは機能しません...他の人への警告として価値があると思います。
まず、一般的な数字の位置は関係ないことに気付きました。
その場合、ハッシュ テーブルを使用して小さなアルゴリズムをスケッチします。各桁に 1 つずつ、10 個のビンを作成します。次に、数字ごとに、その数字に対応する各ビンに数字の ID を (一意に) 入れます。この演算は O(n*k) で、k は数値の桁数です。最後に、すべてのペアを形成するには、各ビン内の数値のペアを取得します。可能性のあるダブロンを削除するには、各ペア (a,b) を
最悪のケースは実際には O(n^2); だと思います。実際、すべてのペアを取りたいので（最大n *（n + 1）/ 2）、このステップにはO（n ^ 2）の複雑さが必要だと思います。したがって、最終的な複雑さは実際には 2 次です。