2

每个有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]}。

我的目标是找出所有可能的 Set 中的 min 和 max 元素，使得 min 和 max 之间的差异最小。

示例 (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

该算法的复杂度为 O(n*k*logn)

仅从每行中选择第一个元素并创建一个最小堆和一个最大堆。

计算当前差值（=head(maxHeap)-head(minheap)）

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

重复此操作，直到其中一个数组中的所有元素都用完。

复杂性：您添加/删除 nk 个元素并且更新最多需要 O(n) 时间。所以复杂度是 O(nklogn)。

注意：这不完全是您的库存堆。minHeap 包含指向 maxHeap 中相同元素的指针，反之亦然。当您从 minHeap 中删除一个元素时，您可以找到指向 maxHeap 的链接并将其删除。同样，每当特定元素的位置发生变化时，都会对另一个堆中的链接进行适当的更改。

于 2013-04-09T21:17:47.390 回答
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}。然后只需选择范围最低的那个。

于 2013-04-09T19:10:21.880 回答
1

将结果集视为一个简单的 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。

现在的过程将是迭代 MultiSet，直到我们使用以下算法达到最低成本：

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

1为了在给定的示例中进行演示，可以通过删除 的最小值（MultiSet 中的最小值低于任何其他行的最小值）将原始成本 20 减少到 18 ，或者通过删除 的最高值来减少到 1419和21（MultiSet 中高于任何其他行的最大值的最高值，即15）来自最后一行。生成的 MultiSet 将是

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

第二次迭代让我们删除12和15将成本降低到 10。

[3 7 11]
[1]
[4]

第三次也是最后一次迭代让我们移除7和11以将成本降低到 3。在第三次迭代之后，全局差异不再能够最小化，因此达到了解决方案。

复杂性？上限为 O(n * m * log(n) * k)

于 2013-04-09T20:18:45.833 回答
1

遍历所有n * k元素。

假设我们当前的元素有 value 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)。

于 2013-04-09T19:04:32.213 回答
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 回答