Geek asks and answers

Finding the minimum distance in the table

I have a m * n dimension table as follows

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

A few limitations in this table:

  • Elements in each row are sorted in ascending order (natural ordering).
  • A -1 means that the cell does not matter for the purposes of calculatio, i.e. there is no element there.
  • No item can appear in a line after -1. A.
  • All cells can have either a positive number from 0 to N, or a -1.
  • There are no two cells with the same positive number, i.e. -1 may appear several times, but no other number can.

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

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

, . O(m^n), . .

+5
2
  • (min-heap).
  • .
  • 2, , "-1". max (S) - min (S) , , S.

- O (m * n * log (m)).

+2

O((m*n)^2 * nlog(m)), :

min <- INFINITY
For each 2 numbers in different rows, let them be a,b
   for each other row: 
        check if there is a number between a and b
    if there is a matching number in every other row:
        min <- min{min,|a-b|}

:
a b O(logm)
O((n*m)^2) a, b.

, , , , "" ( [a, b]) , "" .

: , .

+3

More articles:


All Articles