n個の配列から最小の "n"個の合計

Question

私はこの問題を遭遇し、どこにデータ構造などについての知識を磨くために数年前から私の友人の問題を解決しようとしていました。開始。うまくいけば誰かが私を助けることができた！

n個のソートされていない配列が与えられ、各配列にはn個の要素があります。 Ex。

3 1 2 
7 6 9 
4 9 12 

ここで、各アレイから1つの要素を取り出して追加します。これらの要素の合計を "n-sum"と呼ぶことができます。

n個の最小「n-sum」（重複は許されます）を与えるアルゴリズムを考案する必要があります。私たちの上記の元で

は、答えは次のようになります。与えられた提案の

11, 12, 12 

# 11 comes from: 1 (first array) + 6 (second array) + 4 (third array) 
# 12 comes from: 2 (first array) + 6 (second array) + 4 (third array) 
# 12 comes from: 1 (first array) + 7 (second array) + 4 (third array) 

一つは、プライオリティキューを使用していました。

ありがとうございます！

Answer 1

時間は少なくともO（n^2）です：すべての要素が1000に等しい場合を除いてすべての要素を参照する必要があります。ただし、各行が0の場合を除いて、n要素は0、または最小合計を見つけることができませんでした。

O（n^2 log n）ステップを取って各行をソートします。各行で、行のすべての要素から最初の要素を減算すると、各行の最初の要素は0になります。あなたがそれを補うことができる最小の合計を見つけた後。彼らは第二にKを≤れる限り、順番にすべての値を選択し、最初の行では：あなたの例は

3 1 2 -> 1 2 3 -> 0 1 2 
7 6 9 -> 6 7 9 -> 0 1 3 
4 9 12 -> 4 9 12-> 0 5 7 

ここでM個の​​合計が存在する場合、m個のステップで行うことができるKを≤すべての和を求めるになります2つの行からの合計が≦Kである限り、すべての値を順番に選択します。各行は0で始まるので、時間が無駄になりません。

たとえば、合計≤5は、0 + 0 + 0,0 + 0 + 5,0 + 1 + 0,0 + 3 + 0,1 + 0 + 0,1 + 1 + 0,1 + 3 + 0,2 + 0 + 0,2 + 1 + 0,2 + 3 + 0である。私たちが必要とした3つ以上のもの。 3つの合計≤5を見つけた後で停止すると、「少なくとも3つの合計≤5」が非常に迅速にわかります。一般的なケースでは、n^n個の可能な合計が存在する可能性があるため、早期に停止する必要があります。

K = "2番目の列で最大の要素"を選択すると、すべての0または1つの値以外のすべての0を選択できるので、値がK以下のn + 1個の合計があることがわかります。 2番目の列。あなたの例では、K = 5（我々はそれが働いていることを知っています）。 Xを、n個の合計≤Xがあり、n個の合計≤X - 1より小さい値とする。我々は、0とKとの間のバイナリ検索でXを見つけ、その和を見つける。例：

K = 5は十分に大きいことが知られています。私たちはK = 2を試して、4つの合計を見つけます（実際には3つの合計で停止します）。多すぎる。 K = 1を試行し、0 + 0 + 0、0 + 1 + 0、1 + 0 + 0の3つの解が存在する。我々はK = 0を試すが、1つの解のみである。

この部分は非常に速いので、並べ替えにかかる時間を短縮しようとしています。この場合、最初の2つの列を見るだけで十分でした。私たちは各行に2つの最小アイテムを見つけることができます。この場合は十分です。 2つの最小項目がn個の最小合計を決定するのに十分でない場合、必要な場合には3番目に小さい項目などを見つける。たとえば、最後の行の2番目に大きい項目が5であるため、行の3番目の項目は必要ありません.K≦4の場合、5が合計の要素ではないためです。