配列内の数値の合計が特定の数値になるかどうかを確認する最も効率的な方法は何ですか?たとえば: (5,3,3,9,4) の配列10 を与えるために追加されました (3,3,4) を追加すると、これが発生します
質問する
137 次
1 に答える
0
本当に良い解決策を見つけるには、今よりも多くの時間を費やす必要がありますが、戦略を再考することをお勧めします. @DeepakBala が述べたように、NP 完全な問題を説明しています。
これが異なる点の 1 つは、合計 (Q) が配列内の数値よりも大幅に大きくなる可能性があることです。さらに、3 ～ 150 に制限されているため、2000 の番号を取得すると、多くの重複が発生します。それを有利に活用してください - 作業する前に数を数えてください。149 種類の数について心配するだけで済みます。
なぜそれが重要なのかを考えるために、100 万個の数字を 1 から 100 まで並べ替えてみてください。配列を作成して、各数字が何回表示されるかを数えるだけです。次に、各番号を適切な回数印刷して、リストを再作成します。これは、通常の O(n log(n)) ではなく O(n) です。
最大 2000 個の数値の配列を使用するのではなく、使用可能な各サイズの数と使用中の各サイズの数を示す 150 の配列を検討してください。
Q の 150 以内になるまですべての大きな数を足し合わせてみてください。そして、その差を完全に補うものがあるかどうかを確認してください。それが失敗した場合は、そこからどのように移動するかを考え出す必要があります。
于 2013-04-15T17:58:37.183 に答える