我应该使用什么类型的算法？ [英] What type of algorithm should i use?

问题描述

可以说我有四个组

  

有一个[0，4，9]

     

乙[2,6，11]

     

C [3，8，13]

     

D [7,12]

现在我需要从每个组（即新组）E [A的NUM，B的NUM，C的NUM，D的数字]一个数字，使得E中的最大NUM和最小NUM之间的差异Ë应该问题可能lowest.What类型是什么？其中图算法将更好地解决这类问题呢？ 先谢谢了。

PS：我试图解决这个Java和遗憾的未指定的标题

编辑： 最后，我已经找到了我其实是在寻找 HTTP ：//rcrezende.blogspot.in/2010/08/smallest-relevant-text-snippet-for.html

解决方案

1. 联合每组的内容到了一个阵列。该数组的每个元素应当是一对（号码，组名）。
2. 排序此数组号。
3. 在推进两个迭代器，一个接一个。将第一个迭代器时，并不是每个组的元素，这些迭代器之间。移动第二迭代时，有各组这些迭代之间的一个元素。有关详细信息，请参见这个问题。
4. 在迭代器之间的最小距离确定最佳的结果组（你只需要删除不需要的元素时，有同组的几重presentatives有）。

---

其他的算法：

1. 在每个组的排序元素（如果尚未排序）。
2. 把一对（数，组名），各组的最小元素融入到优先级队列（分堆，优先级=号）。
3. 从队列中取出最小的元素，并将它与来自相同组的下一个元素替换。
4. 重复步骤3，直到没有更多的元素被留在了一些组。计算最大值（队列） - 分钟（队列）对于每次迭代，如果它是比任何previous值越小，更新最好那么远所得组

Lets say I have four group

A [ 0, 4, 9]

B [ 2, 6, 11]

C [ 3, 8, 13]

D [ 7, 12 ]

Now I need one number from each group(i.e a new group) E [num of A,num of B, num of C, num of D], such that the difference between the maximum num in E and minimum num in E should be possible lowest.What type of problem is this ? which graph algorithm will be better to solve this kind of problem ? Thanks in advance.

P.S : I'm trying to solve this in java and sorry for the unspecified title.

Edit : Finally I've found what I'm actually looking for http://rcrezende.blogspot.in/2010/08/smallest-relevant-text-snippet-for.html

解决方案

1. Combine contents of every group into a single array. Each element of the array should be a pair of (number, group name).
2. Sort this array by numbers.
3. Advance two iterators, one after another. Move first iterator when elements of not every group are between these iterators. Move second iterator when there is an element of each group between these iterators. For details see this question.
4. Minimum distance between iterators determine optimal resulting group (you only need to drop unneeded elements when there are several representatives of the same group there).

---

Other algorithm:

1. Sort elements of each group (if not sorted already).
2. Put a pair (number, group name) for smallest elements of each group into priority queue (min-heap, priority=number).
3. Remove smallest element from the queue and replace it with the next element from the same group.
4. Repeat step 3 until no more elements are left in some group. Calculate max(queue) - min(queue) for each iteration and if it is smaller than any previous value, update the best-so-far resulting group.

这篇关于我应该使用什么类型的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！