N 個の数値の配列があります。すべての数字は 1 から k の間です。
問題は、最も頻度の高いトリプレットを見つける最善の方法を見つける方法です。
問題に対する私のアプローチは次のとおりです。
入力が { 1, 2, 3, 4, 1, 2, 3, 4}
最初に、配列の 2 番目の要素から配列の末尾までのトリプレット (1、2、3) の数を検索します。これで、カウントが 1 になります。{ 2, 3, 4) から始めて、配列を検索します。
トリプレットごとに、配列をスキャンしてカウントを見つけます。このように、配列を n-1 回実行します。
このようにして、私のアルゴリズムは n*n 時間の複雑さの順序で実行されます。より良い方法はありますか
この問題。？
最悪の場合の空間と時間の複雑さでそれを行うことができますO(n * log n)。すべてのトリプルをバランスのとれた二分探索木に挿入し、後で最大値を見つけるだけです。
別の方法として、ハッシュ テーブルを使用してO(n)予想時間を取得することもできます (適切なハッシュ関数を選択した場合、これは通常、実際には検索ツリー アプローチよりも高速です)。
メモリ境界はありますか? つまり、メモリ制限のあるデバイスで実行されますか?
そうでない場合は、これが適切な解決策になる可能性があります。配列を反復処理し、トリプル ビルドおよび表現オブジェクト (または C# で実装されている場合は構造体) ごとに、マップにキーとして、トリプル カウンターを値として入力します。
適切に実装hashして機能させると、数字の順序が重要かどうかequalsにかかわらず、「最も人気のある」トリプルを見つけることができます。1,2,3 != 2,1,31,2,3 == 2,1,3
配列全体を反復した後、最大値を見つける必要があり、そのキーが「最も人気のある」トリプルになります。このアプローチでは、X 個の最も人気のあるトリプルも見つけることができます。また、配列を 1 回だけスキャンし、すべてのトリッペルを集計します (トリプルごとに余分なスキャンはありません)。