-2

番号が昇順のkリストがあると考えてください。出力リストの最大数と最小数の差が最小になるように、各リストから1つの数を選択します。

list 1-1,3,5,9,10
list 2-2,4,6,8
list 3-7,11,12,13

出力は5、6、7である必要があります。

5はリスト1から、6はリスト2から、7はリスト3から選択されます。

そのリストの最大数と最小数の差は2、つまり7〜5であるため、kリストがあると考えてください。

4

1 に答える 1

2

でこれを解くことができます。これはO(N*LogK)、Nk 個のリスト内の数字の総数です。

1、0 から始まる各リストのポインターを維持します。

2、現在のポインターを選択した数字と見なし、答えを更新します。

3、最小数のものを選択し、それを1つ増やします（リストの最後に達していない限り）、可能であればステップ2に戻り、それ以外の場合は終了します.

ステップ 2 とステップ 3 では、ヒープを使用して最小数と最大数を維持し、時間を からO(K)に短縮しO(LogK)ます。

于 2012-09-13T08:14:01.493 に答える