发现的最小距离在一个表 [英] Finding the minimum distance in a table

问题描述

我有维数m * n的桌子下面给出

  2 6 9 13
1 4 12 21
10 14 16 -1
 

这个表很少有约束：

1. 在每行中的元素是按递增的顺序（自然 排序）。
2. A -1表示细胞是没有意义的目的 计算中，即，没有元素存在在那里。
3. 在没有元素可以在-1后出现在一排。
4. 所有电池可具有介于0和N或一个正数 -1。
5. 没有两个小区具有相同的正numbe，即-1可以出现 多次但没有其他号码即可。

问：我想找到从表n个数字一组S其中一组必须包含每行只有一个号码和的最大值（S） - 分（S）为尽可能小。

有关如上表给我S = 12,13,14。

我真的AP preciate如果这是可以解决的。我的解决办法是复杂的，它需要 0（M ^ N），这实在是太多了。我想要一个最佳的解决方案。

解决方案

1. 把每一行的所有第一要素的位置为优先级队列（最小堆）。
2. 从队列中取出最小的元素，并将它与来自相同行的下一个元素替换。
3. 重复步骤2，直到没有更多的元素从不同的-1被留在一些行。计算最大值（S） - 。分钟（S）对于每次迭代，如果它是比任何previous值越小，更新最好那么远组S

时间复杂度为O（M * N *日志（M））。

I have a table of dimension m * n as given below

2    6    9    13
1    4    12   21
10   14   16   -1

Few constraints about this table:

1. Elements in each row is sorted in increasing order (natural ordering).
2. A -1 means the cell is of no significance for the purpose of calculatio, i.e. no element exists there.
3. No element can appear in a row after a -1.
4. All the cells can have either a positive number between 0 and N or a -1.
5. No two cells have the same positive numbe, i.e. a -1 can appear multiple times but no other number can.

Question: I would like to find a set S of n numbers from the table where the set must contain only one number from each row and the max(S) - min(S) is as small as possible.

For e.g. the above table gives me S = 12,13,14.

I would really appreciate if this can be solved. My solution is complicated and it takes O(m^n) and this is too much. I want an optimal solution.

解决方案

1. Put positions of all first elements of each row into priority queue (min-heap).
2. Remove smallest element from the queue and replace it with the next element from the same row.
3. Repeat step 2 until no more elements different from "-1" are left in some row. Calculate max(S) - min(S) for each iteration and if it is smaller than any previous value, update the best-so-far set S.

Time complexity is O(m*n*log(m)).

这篇关于发现的最小距离在一个表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！