a、b、c の 3 つのリストがあります。各リストには、ソートされた順序で多数の整数が含まれています。
例のために、次のようにします。
a = [2, 2, 7]
b = [4, 6, 9]
c = [3, 6, 8]
私の目標は、昇順で 3 つのリストから要素のすべての可能な積を列挙することです。
最小限の製品はもちろんa[0]*b[0]*c[0]です。この例では、2 番目に低い製品はa[0]*b[1]*c[0]です。等々。
任意の数のリストの一般的な解決策を見つけようとしています。k 番目に低い製品から (k+1) 番目に低い製品へのステップを一般化するのに苦労しています。
考えられるすべての製品を列挙して並べ替えるわけではありません。これは、非常に多数のリストを扱う可能性があり、上位 1000 の組み合わせだけに関心がある場合があるためです。
教科書へのポインタを含め、どんな助けでも大歓迎です。
はリストの数で、は番目の積O(N * K)であるという時間計算量を取得したいとしましょう。各リストの先頭にポインターを保持します (簡単にするために、これを list の 1 番目のポインター、および1 番目のリストと呼びます)。NKKP[i]iiL[i]i
最初P[i] = 0はリストごとに (リストのインデックスを 0 から開始するため)
Step 1：最初の商品はL[0][P[1]] * L[1][P[2]] * .. L[N][P[N]]です。
Step 2: 次のステップでは、次の積を最小化することに関心があります。j (0<=j<=N)どれL[j][P[j] + 1]が最小かを選択します。でインクリメントP[j]して1からStep 1、次の積を計算します。次の製品がすべての可能性を最小限に抑えるべきであることは明らかだと思います。
一意の製品の数をカウントする場合は、現在の製品が以前の製品と異なる場合にのみインクリメントするカウンターを維持するだけです。
O(log(N) * K)で最小値を取得するためにプライオリティ キューを使用して、このアルゴリズムを に改善することができますStep 2。