找到所有可能的数字组的最大值和最小值之间的最小差值

Question

有n数组的k大小。

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通过从每个数组中随机取任意值来构造。 ，例如一个这样的组可以是{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）是min（1）和max（4）之差为全局最小值或最小值的集合。因此，我们将输出3作为全局最小差异和相应的对（3 4）。如果有多个全局最小值，则将它们全部打印出来。请提出更好的时间和空间复杂度的算法。我们不能采取暴力手段。

Answer 1

遍历所有n * k元素。

说我们当前元素的值为v。假设v是生成的n元组中的最小值，我们来计算最小差值。

二进制搜索的v在其他n - 1阵列（因为他们排序，我们可以做到这一点）的位置，并注意减少它的最佳选择那些大于或等于比v的最小元素的差异对于所有其他阵列。这正是二进制搜索给我们的。

一个例子：

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

如果我们取v = 1第二阵列上，然后我们将在第二拾取3中的第一阵列上，和4。

复杂度为O(N * K * N * log(N)) = O(N^2 * log(N) * K)。

Answer 2

如果我理解正确，您想要找到其元素中的最大差异全局最小的集合。 （我会称该集合的范围）

以k个集合开始，每个集合最初包含第一个数组中的一个元素。对于每个集合，最小值和最大值将等于元素本身。 以您的示例为{3}，{7}和{11}。

然后你继续前进到第二个数组。对于每个集合，您必须从该阵列中选取一个最小化新范围的元素。理想情况下，你会选择一个不增加范围的元素（但现在不可能）。如果这是不可能的，选择扩展您的设置两个方向（加号和减号）的元素。例如，会给你{1-3}，{3-12}，{1-7}，{7-12}，{1-11}和{11-12}。从这些2k集合中，您可以删除重叠的集合。例如，与集合{1-3}相比，集合{1-7}将始终具有更大或相等的范围。您不需要调查{1-7}集。你最终得到集{1-3}和{11-12}。

继续前进到第三个数组，再次选择扩展每个集合的范围尽可能小的元素。你最终得到{1-4}，{11-19}和{4-12}。然后，只需选择范围最低的那个。

Answer 3

考虑结果设置为简单的1XN阵列

[3] 
[1] 
[4] 

其中全球差为3（最大4少最小为1的）。

现在考虑Set的扩展定义，称之为MultiSet。 MultiSet是一个数组，其中每个元素包含一组有序的项目。

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

我们可以计算出全球差异（称之为“成本”）由最大“最后”的每一行的值和最小“第一”的每一行的值之间的差异。在这种情况下，成本会21（max(11,15,21)）和1（min(3,1,4)）之间的差异，这是20

的方法现在将迭代的多集，直到我们达到使用以下算法最小成本：

• 标识具有最低值的行。如果此行只有一个元素，则继续，否则请考虑从该行中删除值低于其他行中的最低值的潜在成本降低。
• 标识具有最高值的行。如果该行只有元素，则继续，否则考虑从该行中删除高于其他行中的最高值的潜在成本降低。
• 删除上面确定的值并继续到下一个最高/最低项目。 -
• 如果最低和最高值都在单项行中，则成本已最小化。

为了演示在给定的例子中，20的原始成本可以通过去除1的最低值（在这比任何其它的行最小低的多集的最低值）降低到18，或降低到通过从最后一行中除去最高值19和21（MultiSet中高于任何其他行的最大值的最高值，即15）。得到的多集是

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

第二次迭代我们已经删除12和15的成本降低到10

[3 7 11] 
[1] 
[4] 

第三和最后的迭代有我们删除7和11到将成本降低到3.第三次迭代后，全局差异不能再最小化，从而达到解决方案。

复杂性？上被O为界（N * M *的log（n）* K）

Answer 4

该算法的复杂度是O，从各行（N * K * logn）时间

仅选择第一元件，并创建一个最小堆和一个最大的堆。

计算电流差（=头（maxHeap）-head（minheap））

删除minHeap的头部（以及从maxHeap相应元素），并添加从相应的数组的下一个元素（对应于删除元素）到minHeap和maxHeap。

重复该操作直到阵列中的所有元素都耗尽。

复杂性：您添加/删除nk个元素，更新最多需要O（n）个时间。所以复杂性是O（nklogn）。

注意：这不完全是你的股票堆。 minHeap包含指向maxHeap中相同元素的指针，反之亦然。当您从minHeap中删除元素时，您可以找到指向maxHeap的链接并将其删除。此外，无论何时某个元素的位置发生更改，都会对另一个堆中的链接进行适当更改。

Answer 5

代码：

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; 
}