0

好吧，我已经得到了许多元素对(s,h)，其中在二维数组的第 - 行s发送一个h元素。s不必每行具有相同数量的元素，只知道不能超过一行中的 N 个元素。

我想要做的是找到第一行的某个元素与其他元素之间的最小最大差异（！）。

因此，如果我有 3 行，而(101,92) (100,25,95,52,101) (93,108,0,65,200)我想要找到的是 3，因为我必须选择 92，我从第一到第二有 95-92=3，从第一到第三有 93-92=1。

我已经达到了一个点，如果我有每个元素的s行和，那么在从第一行向其他行选择最佳拟合时，可以有一个良好的平均性能场景。n(i)i=0..sn0<=n1<=...<=ns

但是，在某些情况下，我想不出低于 O(n 2 ) 甚至可能是 O(n 3 ) 的方法。有没有人建议一种相当改进的方法来做到这一点？

4

1 回答 1

1

将所有行合并到一个列表中，同时跟踪哪个元素来自哪里。

对这个列表进行排序。

每行都有一个最后一个值变量。

对于排序列表中的每个项目，更新适用列表的最后一个值变量。如果并非所有行都设置了最后一个值，则什么也不做。如果它是第一个列表中的元素：

  • 重新计算所有最后值变量的最大差异。存储此差异。

如果它是任何其他列表中的元素：

  • 如果之前没有设置所有值，则计算最大差值。否则，如果第一个列表的 last-value 和这个元素之间的差异大于最大差异，则用这个差异更新最大差异。存储此差异。

最小的差异是期望值。

例子：

Lists: (101,92) (100,25,95,52,101) (93,108,0,65,200)

Sorted  0  25 52 65 92 93 95 100 101 101 108 200
Source  2  1  1  2  0  2  1  1   0   1   2   2

Last[0] -  -  -  -  92 92 92 92  101 101 101 101
Last[1] -  25 52 52 52 52 95 100 100 101 101 101
Last[2] 0  0  0  65 65 93 93 93  93  93  108 200

Diff    -  -  -  -  40 41 3  8   8   8   7   9
Best    -  -  -  -  40 40 3  3   3   3   3   3

最佳 = 3 根据需要。存储实际物品或事后查找它们应该很容易。

复杂：

设n为项目总数，k为列表数。

O(n log n)对于组合+排序。

O(nk)（最坏的情况）扫描，因为我们正在检查n项目，并且在每个项目上，我们都做了最大O(k)的工作。

所以O(n log n + nk)。

于 2013-05-08T07:49:25.467 回答