1

这是一个家庭作业问题，但我错过了讲师解释解决方案的讲座，我仍然无法弄清楚......

如果给定区间 [0,1] 中的 n 个实数（即 x1，x2，x3，...，xn），则表明存在一种算法，该算法在最坏情况下运行的线性时间给出了这些 n 个数的排列这样相邻数字的差之和小于 2。给出的提示是“桶”。

4

3 回答 3

2

好吧，你可以走这条路。分割[0, 1]成k段：[0, 1/k), [1/k, 2/k), ..., [(k-1)/k, 1].

您现在浏览您的列表并首先将所有适合第一段的数字放入一个新列表，然后放入第二段等。这可以一次性完成，所以O(n).

考虑一下现在需要的金额是多少。同一段内1/k数字的差异最多是这种差异的数量n-(k-1)。其余的(n-1)差异在来自相邻存储桶的数字之间，总共（很清楚，为什么？）不超过1. 总和受 约束(n-k+1)/k + (k-1)/k。如果足够小，您可以制作足够k大。

更多细节：

让我们将我们的差异绘制成 2 种颜色：来自同一段的数字之间的差异被绘制为蓝色，而来自不同段的数字之间的差异被绘制为红色。由于排序，我们首先只有第 1 段中的数字（可能为 0），然后是第 2 段中的数字，依此类推。因此，我们首先有一些蓝色差异，然后是红色差异，然后是几个蓝色差异，然后是红色差异等。

让我们看看红色差异的数量是多少。显然不只是k-1红色的差异，对吧？因为每个红色差异都会从一个段跳到更高的段。其余的差异是蓝色的。

现在，每个蓝色差异不超过1/k，因为被减数和减数来自同一段。并且所有红色差值（即它们的总和！）总共不超过 1。（暂时跳过其余部分，因为这是一道作业题。）

更正：
所有红色差异的总和不超过 2-2/k。这是为什么？走着瞧。在最坏的情况下，第一个红色差异可能是从某个段的开头A到某个其他段的结尾B。第二个是在最坏的情况下从某个其他段的开始到结束。因此，在差异总和中，除了第一个和最后一个段之外，每个段最多计算两次。BC

于 2012-04-12T13:27:08.857 回答
0

尝试将区间拆分为 n 个等长区间。现在将数字按任意顺序放入它们所属的区间中，并证明这可以解决您的问题。

于 2012-04-12T13:23:46.010 回答
-1

你学过桶排序吗？http://en.wikipedia.org/wiki/Bucket_sort

还要看看排序数组的行为：{ 0, .5, .75, 1 } ：差异之和为 1。

将其与未排序数组的行为进行比较： { .75, .5, 0, 1 } ：差值之和为 1.75

于 2012-04-12T13:24:03.573 回答