0

並べ替えられた配列が与えられた場合n、新しい配列内の数値の最大値と最小値の差が最小になるように、各配列から 1 つの数値を選択して新しい配列を作成します。

n=3入力配列の例:

A = {4, 10, 15}
B = {1, 13, 29}
C = {5, 14, 28}

この場合、答えは15、配列 A、13配列 B、および14配列 C から選択max[{15, 13, 14}] - min[{15, 13, 14}] = 15 - 13 = 2することになります。これは、最大最小差が 2 未満になる組み合わせが他にないためです。

最も効率的なアルゴリズムは何ですか?

4

3 に答える 3

3

A1、A2、... An を n 個の配列とします。
すべての配列がソートされていると仮定すると、そうでない場合は個別にソートできます。

S = [ A1[0], A2[0],...An[0] ]
minSpread = max{S} - min{S}
Iterate i = 1 to L (where L is length of shortest array)
   Remove min{S} from S.
   Insert Ak[i] in S. (where Ak is the kth array from which a value was removed in previous step.)
   minSpread = min(minSpread, max{S} - min{S});

スプレッド (最大 - 最小) を最小化する必要があるため、現在の最小値を削除して最小値を「上に」絞るしかありません。

O(N) + O(N*L*logN) で計算されます。N は no です。配列の長さで、L は最短の配列の長さです。

これは、検索結果の表示中によくある問題です。指定されたすべての検索語を含むページからの抜粋の可能な限り小さいウィンドウを表示する必要がある場合。
ここで、A1[] A2[]... An[] には、単語 say-W1、W2... Wn の出現のインデックスが含まれています。

編集：

ニモ：その通りです。証明は少し複雑です。あなたが提供したリンクは、同様の解決策を試みています。追加できるのは次のとおりです。

事実を考慮する:
1. 各配列から正確に 1 つの要素を維持する必要があります。
2. 配列はすべて昇順でソートされます。
多くの組み合わせをすぐに破棄して、すべての組み合わせを生成するよりも良い時間で破棄できるようにしてください。詳細については、「Nemo」が提供するリンクを参照してください。

そして、提案されているように最小ヒープを維持することで、複雑さを O(N) + O(N*L*logN) に下げることができます。
ここで、N はいいえです。L は最短配列の長さです。

于 2012-10-18T22:29:21.657 に答える
0

これは、再帰的なバックトラッキング アプローチによって解決できます。

Best = OO
ChoiceArr = [ ]

function rec(i)
       if (i == numArrays)
          calc()
       else
           for j = 0 to Arrays[i].length - 1
               ChoiceArr[i] = Arrays[i][j]
               rec(i + 1)

function calc()
     mn = OO
     mx = -OO
     for i = 0 to ChoiceArr.length - 1
          mn = min(mn, ChoiceArr[i])
          mx = max(mx, ChoiceArr[i])

     Best = min(Best, mx - mn)

複雑さは指数関数的です: O(m ^ n)、mはサブ配列の最大サイズ、nはサブ配列の総数です。これは、 nが大きくなるにつれて非常に急速に大きくなり、多くの時間を消費する可能性があります。

于 2012-10-18T21:51:02.860 に答える
0
  1. すべての配列のすべての要素を新しい配列にコピーします。要素には、元の配列の値と元の配列の一意の識別子が含まれます。の上）
  2. 新しい配列を値 O(n log n) で並べ替えます
  3. 新しい配列を反復処理します。最初と最後のメンバーの差が最小で、すべての元の配列のメンバーも含むシーケンスを見つけます。O(n^2)

C# 実装

var arr1 = new[] { 4, 10, 15 };
var arr2 = new[] { 1, 13, 29 };
var arr3 = new[] { 5, 14, 28 };

var sortedAndIndexed = arr1
    .Select(x => new { value = x, array = 'a' })
    .Concat(arr2.Select(x => new { value = x, array = 'b' }))
    .Concat(arr3.Select(x => new { value = x, array = 'c' }))
    .OrderBy(x => x.value)
    .ToList();

var numberOfArrays = 3;
var minValue = sortedAndIndexed.Last().value - sortedAndIndexed.First().value;
var bestSlice = new[] { 0, sortedAndIndexed.Count - 1 };
for (int i = 0; i < sortedAndIndexed.Count; i++)
{
    var seen = new HashSet<char>();
    var firstItem = sortedAndIndexed[i];
    seen.Add(firstItem.array);
    int j = i + 1;
    for (; j < sortedAndIndexed.Count && 
           seen.Count < numberOfArrays && 
           sortedAndIndexed[j].value - firstItem.value < minValue; j++)
    {
        seen.Add(sortedAndIndexed[j].array);
    }
    if (seen.Count == numberOfArrays)
    {
        j -= 1;
        int value = sortedAndIndexed[j].value - firstItem.value;
        if (value < minValue)
        {
            minValue = value;
            bestSlice = new[] { i, j };
        }
    }
}

var arraySeen = new HashSet<char>();
var sliceElements = new List<int>();
for (int i = bestSlice[0]; i <= bestSlice[1]; i++)
{
    var item = sortedAndIndexed[i];
    if (arraySeen.Add(item.array))
    {
        sliceElements.Add(item.value);
    }
}
var elements = sliceElements
      .Select(x => x.ToString())
      .ToArray();
var result = String.Join(", ", elements);
Console.WriteLine("Best slice: "+ result);

出力：

Best slice: 13, 14, 15
于 2012-10-18T22:46:23.933 に答える