arrays - 配列内で繰り返される部分配列の数を見つける

Question

0-nからの要素を含む (つまり、サイズ = n)からインデックス付けされた配列があります0-m( m < nm は n の 100 倍または 1000 倍小さい、つまり m は n よりもはるかに小さいと仮定します)。そのため、多くの要素またはサブ配列を繰り返す必要があり、を使用して、サイズが 1 または 1 を超える繰り返しサブ配列の数を見つけます。たとえば、配列を考えてみます。
1 2 4 1 2 4 1 5 6 3 5ここで
1は、 が 2 回繰り返されます。 は
21回繰り返されます。 は
41
5回
1 2繰り返さ
2 4れ
4 1ます。繰り返される 1 回
1 2 4が繰り返される 1 回
2 4 1が繰り返される 1 回が繰り返される 1 回
1 2 4 1が繰り返される
したがって、最終的な答えはこれらの合計、つまり 11 です。
これを解決するためのデータ構造または効率的なアルゴリズムを提案してください。m をハッシュして、それが発生するインデックス値に注意することを考えていましたが、形式化していませんでした。
推定n,m < 10^5

Answer 1

1. キーとして整数を持ち、値として整数の拡張可能なリスト (リンクされたリストなど) を持つハッシュを作成します。

2. 入力リストを読みます。スキャンされる各入力要素をキーとして扱います。次の要素のインデックスを関連する値のリストに追加します。

3. これで、繰り返される 1 要素の数は n - |keys| になります。

4. 次に、キーを調べます。キーごとに、元のリストのインデックス付き要素を新しい入力リストとして扱います。新しいハッシュを作成し、手順 1 と同様に続行します。インデックスを保存するときは、元のリストのインデックスを引き続き使用することに注意してください。

例: 1 2 4 1 2 4 1 5 6 3 5 (インデックスがゼロであると仮定します)。ここで、n=11 です。

• 1 -> [1, 4, 7]
• 2 -> [2, 5]
• 3 -> [10]
• 4 -> [3, 6]
• 5 -> [8, なし]
• 6 -> [9]

繰り返される 1-elt の数は、11 - 6 = 5 です。

次に、キーを見ていきます。1 から始めます。インデックス リストは [1, 4, 7] で、要素 [2, 2, 5] に対応します。

• 2 -> [2, 5]
• 5 -> [8]

これにより、3 - 2 = 1 つの重複する 2 要素リストが取得されます。

等...

実行時間: 入力 + 出力で線形