0

给定n已排序的数组，通过从每个数组中选择一个数字来创建一个新数组，以使新数组中数字的最大值和最小值之间的差异最小化。

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 为否。数组和 L 是最短数组的长度。

这是显示搜索结果时的常见问题。当我们必须显示包含所有给定搜索词的页面摘录的最小可能窗口时。
这里，A1[] A2[]...An[] 包含单词say-W1，W2...Wn 出现的索引。

编辑：

尼莫：你说得对。证明有点牵强。您提供的链接尝试了类似的解决方案。我能补充的是：

考虑以下事实：
1. 我们必须从每个数组中准确地维护一个元素。
2. 数组全部按升序排列。
因此，帮助我们立即丢弃许多组合，与生成所有组合相比，可以在更好的时间内完成它。有关更多详细信息，请访问“Nemo”提供的链接。

并且，通过按照建议维护一个 minheap，可以将复杂性降低到 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 回答