最小范围3套

Question

我们有三套S1，S2，S3。我需要找到X，Y，Z，使得 XëS1 ýËS2 Z E - S3

让分表示出来的x，y的最小值，Z 让最大值表示最大值出x的，Y，Z 由最大最小表示的范围应是最小的可能值

Answer 1

min = infinity (really large number in practice, like 1000000000) 
solution = (-, -, -) 
for each x E S1 
    for each y E S2 
     for each z E S3 
      t = max(x, y, z) - min(x, y, z) 
      if t < min 
       min = t 
       solution = (x, y, z) 

Answer 2

当然，通过IVlad描述的全暴力破解的解决方案是简单，因此，更容易和更快地写，但它的复杂性是O(n3)。

根据您的algorithm标签，我想发布一个更复杂的算法，具有O(n2)最坏情况和平均O(nlogn)复杂性（几乎可以肯定这一点，但我懒得作证明）。

算法描述

考虑想一些抽象(X, Y, Z)元组。我们想要找到一个元组，它的最大元素和最小元素之间的最小距离为。我们现在可以说的是，距离实际上是由我们的最大元素和最小元素创建的。因此，只要它介于最大值和最小值之间，它们之间的元素的值并不重要。

所以，这里是方法。我们分配一些额外的集合（我们称之为S）并将每个初始集合（X,Y,Z）合并成一个集合。我们还需要能够查找我们刚创建的集合中每个元素的初始集合（因此，如果我们指向S中的某个元素，比如说S[10]并询问“这个人从哪里来？”，我们的应用程序应该回答类似“他来自Y）。

之后，让我们来梳理我们的新集S由它的键（这将是为O（n log n）的或为O（n）的某些情况下）

确定迷你mal distance

现在有趣的部分来了。我们想要做的是计算一些人工值，我们称它为最小距离并将其标记为d[x]，其中x是S中的某个元素。该值是指使用序列中当前元素的前置元素/后继元素可以实现的最小距离。

请看下面的例子 - 这是我们S集（第一行显示的索引，第二个 - 价值观和信件X，Y和Z指初始套）：

0 1 2 3 4 5 6 7 
------------------ 
1 2 4 5 8 10 11 12 
Y Z Y X Y Y X Z 

比方说，我们要计算的是我们的索引为4的元素的最小距离为。实际上，最小距离意味着可以使用所选元素构建的元组。

在我们的例子（S[4]），我们可以说，我们的(x, y, z)对肯定会像(something, 8, something)，因为它应该有，我们正在计算距离的（很明显的，嘿嘿）的元素。我们不得不填补空白。我们知道我们正在寻找的元素应该是从X和Z。我们希望这些元素在max - min的距离上是最好的。有一个简单的方法来选择它们。

我们进行双向运行（向左运行，从当前元素运行）寻找第一个元素，而不是从Y。在这种情况下，我们会在两个方向上寻找X和Z中两个最近的元素（总共4个元素）。

这一发现方法正是我们需要的：如果我们选择X同时运行（左/右，无所谓）的第一个元素，该元素将西装我们比它后面的任何其他元素更好距离条款。发生这种情况是因为我们的S集已排序。

以我示例的情况下（计数的距离为元件与索引号4），我们将标志着与索引6和7作为适合从右侧，并与索引从左侧1和3元素的元素。

现在，我们必须测试4个可能发生的情况 - 并采取这种情况，以便我们的距离最小。在我们的特定情况下，我们有以下的（由前一程序返回的元素）：

Z X Y X Z 
2 5 8 11 12 

我们要测试，可以使用这些要素来构建每一个（X，Y，Z）元组，采取与最小距离的元组并为我们的元素保存这个距离。在这个例子中，我们会说(11, 8, 12)元组的最佳距离为4。所以，我们店d[5] = 4（5这里是元素索引）。

退让的结果

现在，当我们知道如何找到的距离，让我们做它的每一个元素在我们的S集（此操作将采取O(n2)在最坏的情况下，更好的时间 - 这是如平均为O(nlogn)）。

后，我们有一个在我们设定的每一个元素距离值，只是最小距离选择元素，并再次运行我们的距离计数算法（这是上述）它，但现在保存(-, -, -)元组。这将是答案。

伪

这里来的伪代码，我试图使它易于阅读，但它的实施将更加复杂，因为你需要的代码集查找*（“确定设置元素“）。还要注意，确定元组并确定距离例程基本相同，但第二个产生实际的元组。

COMBINE (X, Y, Z) -> S 
SORT(S) 

FOREACH (v in S) 
    DETERMINE_DISTANCE(v, S) -> d[v] 

DETERMINE_TUPLE(MIN(d[v])) 

P.S

我敢肯定，这种方法可以很容易地用于（ - ， - ， - ，... - ）元组求，仍然产生良好的算法复杂度。