一种算法，给出数的排列，使得相邻差值之和小于2

Question

这是一道家庭作业题，但我错过了讲师讲解答案的课，我还是想不通……

如果给定区间内的n个实数，0,1显示有一个算法在最坏的情况下线性时间内运行，它给出了这n个数的排列，使得相邻数的差值之和小于2。给出的提示是“bucket”。

Answer 1

嗯，你可以走这条路。将[0, 1]拆分为k段：[0, 1/k)、[1/k, 2/k)、...、[(k-1)/k, 1]。

你现在浏览你的列表，并把所有适合第一段的数字放入一个新的列表中，然后放入第二段的数字，依此类推。这可以在一遍中完成，所以O(n)。

考虑一下现在所需的金额是多少。同一段内的数字之差至多为1/k，即这种差异的数目n-(k-1)。rest (n-1)的不同之处在于来自相邻存储桶的数字之间(清楚了吗，为什么？)不会超过1。总和由(n-k+1)/k + (k-1)/k绑定。对于k来说，如果足够小，您可以使其足够大。

更多详细信息：

让我们将差异绘制成两种颜色:来自同一段的数字之间的差异被涂成蓝色，而来自不同段的数字之间的差异被涂成红色。由于排序，我们首先只有第一段中的数字(可能是0)，而不是第二段中的数字，依此类推。所以，我们首先有一些蓝色的差异，比红色的差异，然后再几个蓝色的差异，再一次红色的差异，等等。

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

现在，每个蓝色差不超过1/k，因为被减数和减数来自同一段。以及所有的红色差异(就是它们的总和！)不要超过1。(暂时跳过其余部分，因为这是一个家庭作业问题。)

更正：

所有红色差异的总和不超过2-2/k。为什么？好吧，让我们看看。在最坏的情况下，第一个红色差异可能是从某一段A的开头到某一其它段B的结尾。第二个是在最坏的情况下，从B的开始到其他一些段C的结束。因此，在差值的总和中，除了第一个和最后一个片段之外，每个片段最多计数两次。

Answer 2

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

Answer 3

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

另请看排序数组的行为：{ 0，.5，.75，1 }：差之和为1。

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