我有维数m * n的桌子下面给出
2 6 9 13
1 4 12 21
10 14 16 -1
这个表很少有约束:
在每行中的元素是按递增的顺序(自然 排序)。 A -1表示细胞是没有意义的目的 计算中,即,没有元素存在在那里。 在没有元素可以在-1后出现在一排。 所有电池可具有介于0和N或一个正数 -1。 没有两个小区具有相同的正numbe,即-1可以出现 多次但没有其他号码即可。问:我想找到从表n个数字一组S其中一组必须包含每行只有一个号码和的最大值(S) - 分(S)为尽可能小。
有关如上表给我S = 12,13,14。
我真的AP preciate如果这是可以解决的。我的解决办法是复杂的,它需要 0(M ^ N)
,这实在是太多了。我想要一个最佳的解决方案。
时间复杂度为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:
Elements in each row is sorted in increasing order (natural ordering). A -1 means the cell is of no significance for the purpose of calculatio, i.e. no element exists there. No element can appear in a row after a -1. All the cells can have either a positive number between 0 and N or a -1. 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.
Time complexity is O(m*n*log(m)).