2

それぞれkサイズのn 個の配列があります。

a0[0],a0[1],......a0[k-1]
a1[0],a1[1],......a1[k-1]
.
.
.
an-1[0],an-1[1], .... an-1[k-1]

重複はまったくなく、すべての配列がソートされています。

これで、各配列から任意の値をランダムに取得して、サイズnのセットが構築されます。たとえば、そのようなセットの 1 つを にすることができます{a0[0],a1[3],a2[2],.... an-1[k-1]}。

私の目標は、可能なすべてのセットの最小要素と最大要素を見つけて、最小値と最大値の差が最小になるようにすることです。

例 (k=3、n=3)

[3 7 11]
[1 12 15]
[4 19 21]

したがって、数学的には、そのようなセットは 27 になります。

(3 1 4) (3 12 4) (3 15 4)
(3 1 19) (3 12 19) (3 15 19)
(3 1 21) (3 12 21) (3 15 21)

(7 1 4) (7 12 4) (7 15 4)
(7 1 19) (7 12 19) (7 15 19)
(7 1 21) (7 12 21) (7 15 21)

(11 1 4) (7 12 4) (11 15 4)
(11 1 19) (7 12 19) (11 15 19)
(11 1 21) (7 12 21) (11 15 21)

これらすべてのセットの最小値と最大値を計算した後、(3 1 4) は、最小 (1) と最大 (4) の差がグローバルな最小値または最小値であるセットであると結論付けることができます。

したがって、グローバル最小差として 3 を出力し、対応するペア (3 4) を出力します。複数の大域的最小値がある場合は、それらをすべて出力します。より良い時間と空間の複雑さを持つアルゴリズムを提案してください。力ずくでアプローチすることはできません。

4

5 に答える 5

2

私の理解が正しければ、その要素内の最大の差が全体的に最小であるセットを見つけたいと考えています。（セットの範囲と呼びます）

k 個のセットから始めます。各セットには、最初の配列の要素が最初に含まれています。各セットの最小値と最大値は、要素自体に等しくなります。あなたの例では、{3}、{7}、{11} になります。

次に、2 番目の配列に進みます。セットごとに、その配列から新しい範囲を最小化する要素を選択する必要があります。理想的には、範囲を増加させない要素を選択します (ただし、現在は不可能です)。それが不可能な場合は、セットを両方向 (プラスとマイナス) に拡張する要素を選択します。{1-3}、{3-12}、{1-7}、{7-12}、{1-11}、および {11-12} を与える例については。これらの2kセットから、重複しているセットを削除できます。たとえば、セット {1-7} の範囲は、セット {1-3} と比較して常に大きいか同じです。{1-7} セットを調査する必要はありません。セット {1-3} と {11-12} になります。

3 番目の配列に移り、各セットの範囲をできるだけ小さく拡張する要素を再び選択します。最終的に {1-4}、{11-19}、{4-12} になりました。次に、範囲が最も低いものを選択します。

于 2013-04-09T19:10:21.880 に答える
2

このアルゴリズムの複雑さは O(n*k*logn) です

各行から最初の要素のみを選択し、最小ヒープと最大ヒープを作成します。

現在の差分 (=head(maxHeap)-head(minheap)) を計算します。

minHeap (および maxHeap の対応する要素) の先頭を削除し、対応する配列 (削除された要素に対応する) の次の要素を minHeap と maxHeap の両方に追加します。

配列の 1 つですべての要素が使い果たされるまで、それを繰り返します。

複雑さ: nk 個の要素を追加/削除すると、更新には最大で O(n) 時間かかります。したがって、複雑さは O(nklogn) です。

注: これは正確にはストック ヒープではありません。minHeap には maxHeap の同じ要素へのポインタが含まれ、その逆も同様です。minHeap から要素を削除すると、maxHeap へのリンクを見つけて削除することもできます。また、特定の要素の位置が変更されるたびに、他のヒープ内のリンクに適切な変更が加えられます。

于 2013-04-09T21:17:47.390 に答える
1

n * kすべての要素を反復します。

現在の要素に value があるとしますv。v結果のnタプルの最小値であると仮定して、最小差を計算しましょう。

v他の配列の位置をバイナリ検索し(並べ替えられているので実行できます)、差を減らすには、他のすべての配列n - 1以上の最小の要素を選択するのが最適であることに注意してください。vこれはまさに二分探索が私たちに与えるものです。

例：

[3 7 11]
[1 12 15]
[4 19 21]

2 番目の配列を使用する場合はv = 1、最初の配列で 3 を選択し、2 番目の配列で 4 を選択します。

複雑さはO(N * K * N * log(N)) = O(N^2 * log(N) * K).

于 2013-04-09T19:04:32.213 に答える
1

結果セットを単純な 1xn 配列と見なす

[3]
[1]
[4]

ここで、全体的な差は 3 です (最大 4 から最小 1 を引いたもの)。

Set の拡張定義を考えてみましょう。これを MultiSet と呼びます。MultiSet は、各要素がアイテムの順序付けられたセットを含む配列です。

[3 7 11]
[1 12 15]
[4 19 21]

各行の最大の「最後の」値と各行の最小の「最初の」値の差によって、全体的な差 (「コスト」と呼びます) を計算できます。max(11,15,21)この場合、コストは 21 ( ) と 1 ( )の差のmin(3,1,4)20 になります。

プロセスは、次のアルゴリズムを使用して最小コストに達するまで MultiSet を反復することです。

  • 値が最も低い行を識別します。この行に要素が 1 つしかない場合は続行します。それ以外の場合は、他の行の最小値よりも低い値をこの行から削除することでコストを削減できる可能性があることを考慮してください。
  • 最も高い値を持つ行を識別します。この行に要素しかない場合は続行します。それ以外の場合は、他の行の最大値よりも高い値をこの行から削除することでコストを削減できる可能性があることを考慮してください。
  • 上記の値を削除し、次に高い/低い項目に進みます。-
  • 最小値と最大値の両方が単一項目の行にある場合、コストは最小化されています。

与えられた例で示すために、20 の元のコストは、最小値1(他の行の最小値よりも低い MultiSet の最小値) を削除することによって 18 に減らすことができます。または、最大値を削除することによって 14 に減らすことができます。19および21(他のどの行の最大値よりも高い MultiSet 内の最大値、つまり15) 最終行から。結果の MultiSet は次のようになります。

[3 7 11]
[1 12 15]
[4]

122 回目の反復では、 andを削除して15、コストを 10 に減らします。

[3 7 11]
[1]
[4]

そして、最後の 3 回目の反復では7andを削除し11て、コストを 3 に減らします。

複雑さ？O(n * m * log(n) * k) による上限

于 2013-04-09T20:18:45.833 に答える
0

コード：

private static ElementData calcMin(int[] n1Arr, int[] n2Arr, int[] n3Arr) {

    ElementData data = new ElementData();// added just to know which two elements algo has picked

    int[] mixArr = { n1Arr[0], n2Arr[0], n3Arr[0] };
    Arrays.sort(mixArr);
    int minValue = mixArr[2] - mixArr[0];

    data.setMinValue(minValue);
    data.setHighValue(mixArr[2]);
    data.setLowValue(mixArr[0]);

    int tempValue = 0;
    for (int n1 : n1Arr) {

        for (int n2 : n2Arr) {

            for (int n3 : n3Arr) {

                int[] mixArr1 = { n1, n2, n3 };
                Arrays.sort(mixArr1);

                tempValue = mixArr1[2] - mixArr1[0];
                if (minValue > tempValue) {
                    minValue = tempValue;

                    data = new ElementData();
                    data.setMinValue(minValue);
                    data.setHighValue(mixArr1[2]);
                    data.setLowValue(mixArr1[0]);
                }
            }
        }
    }
    return data;
}
于 2015-11-05T04:54:14.953 に答える