查找最大和数字的所有可能的套最小值之间至少差 [英] Finding least difference between max and min value of all possible sets of numbers

问题描述

有 N 的阵列的 K 的每一个尺寸。

There are n arrays of k size each.

a0[0],a0[1],......a0[k-1]
a1[0],a1[1],......a1[k-1]
.
.
.
an-1[0],an-1[1], .... an-1[k-1]

有没有重复的一切，所有的阵列进行排序。

There are no duplicates at all and all the arrays are sorted.

现在一集大小的 N 的是通过采取任何值，随机从每个阵列构成。 例如，一个这样的组可以是 {A0 [0]，A1 [3]，A2 [2]，....一个-1- [K-1]}

Now a Set of size n is constructed by taking any value randomly from each of the arrays. e.g one such set can be {a0[0],a1[3],a2[2],.... an-1[k-1]}.

我的目标是找出在所有可能的设置的最小和最大的元素，使得所述最小和最大之间的差异是最低的。

My goal is to find out the min and max elements in all possible Sets such that the difference between the min and max is the lowest.

例（K = 3，N = 3）

Example (k=3,n=3)

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

所以，数学将有27组这样

So mathematically there will be 27 such sets

(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）和max之间差（4）是全局最小或最低

After computing min and max values of all these sets we can conclude that (3 1 4) is the set for which difference between min (1) and max (4) is the global minimum or lowest.

因此​​，我们将输出3作为全局最小值差和相应的一对，它是（3〜4）。如果有多个全局最优，然后全部打印出来。请提出的算法具有较好的时间和空间复杂度。我们不能去强制方法。

So we will output 3 as the global minimum difference and the corresponding pair which is (3 4). If there are multiple global minima then print them all. Please suggest the algorithm with better time and space complexity. We can't go for brute force approach.

推荐答案

该算法的复杂度为O（n * K * LOGN）

Complexity of this algorithm is O(n*k*logn)

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

Select only the first element from each row and create a min heap and a max heap.

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

Calculate the current difference (=head(maxHeap)-head(minheap))

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

Remove the head of minHeap (and the corresponding element from maxHeap) and add the next element from the corresponding array (corresponding to removed element) to both minHeap and maxHeap.

重复，直到在阵列中的一个都用尽了所有的元素。

Repeat it until all the elements in at one of the array are exhausted.

复杂性：你添加/删除NK元素和更新需要O（n）的时间最多。所以复杂度为O（nklogn）。

Complexity: You add/remove nk elements and update takes O(n) time at most. So complexity is O(nklogn).

请注意：这不正是你的股票堆。该minHeap包含指针，指向maxHeap，反之亦然相同的元素。当你删除minHeap一个元素，你可以找到的链接maxHeap并删除它。此外，每当特定元素的变化位置，适当的改变在其他堆的链接进行。

Note: It is not exactly your stock heap. The minHeap contains pointer to the same element in maxHeap and vice versa. When you delete an element from minHeap, you can find the link to the maxHeap and delete it too. Also whenever position of a particular element changes, appropriate changes are made to the link in the other heap.

这篇关于查找最大和数字的所有可能的套最小值之间至少差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！