2013-01-03 10 views
5

私たちはN個の数字の配列を持っています。すべての数字は1-kの間です。配列内で最も頻繁な三つ組を見つける

問題は、最も頻繁なトリプレットを見つける最良の方法を見つける方法です。

問題への私のアプローチがある:

セイ入力トリプレットのカウント用

{4、3、2、1、4、3、2、1}のように最初の検索である場合( 1、2、3)は、配列の2番目の要素から配列の最後まで開始します。今度はカウントを1にします。 {2、3、4}で始まり、配列を検索してください。

各トリプレットについて、アレイをスキャンしてカウントを見つけます。このように、n-1回アレイを実行します。

この方法では、アルゴリズムはn * n時間の複雑さの順に実行されます。何か良い方法がありますか?

この問題はありますか?

+2

「トリプレット」の定義は何ですか?順番に3つの数字がありますか、連続する3つの整数だけですか? '3,4,1'はトリプレットですか? –

+0

予想された空間の複雑さは何ですか? – jackalope

+0

あなたはあなたが必要とする「トリプレット」を知っていますか、それを見つけるためにアルゴを意図していますか? – bonCodigo

答えて

4

これは、最悪の場合の空間と時間の複雑さで行うことができます。バランスのとれたバイナリ検索ツリーにすべてのトリプルを挿入し、その後最大値を見つけます。

また、ハッシュテーブルを使用してO(n)の予想時間を取得することもできます(実際には、良いハッシュ関数を選択すると、実際には検索ツリーアプローチよりも高速です)。

2

メモリ境界はありますか?つまり、メモリ制限のあるデバイスで実行されますか?

もしそうでなければ、これは良い解決策になるかもしれません。マップ上のキーとトリプルカウンターを値としてマップに入れた配列と各トリプルビルドと表現オブジェクト(またはc#で実装されている構造体)

hashequalsの機能が適切に実装されていれば、数字の順序が重要であるかどうかなど、「最も一般的な」トリプルを見つけることができます。 1,2,3 != 2,1,3または1,2,3 == 2,1,3

配列全体を反復した後は、最大値を見つける必要がありますし、その鍵は、あなたの「最も人気のある」トリプルだろう。このアプローチでは、Xの最も一般的なトリプルも見つかるはずです。また、アレイを一度だけスキャンし、すべてのトリッペルを集約します(各トリプルの余分なスキャンはありません)。

関連する問題