给出数字排列的算法，使得相邻差异的总和小于 2

Question

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

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

Answer 1

嗯，你可以往这边走。将[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 足够大。

---

更多详情:

让我们将差异涂成两种颜色:同一部分的数字之间的差异涂成蓝色，不同部分的数字之间的差异涂成红色。由于排序，我们首先只有第 1 段中的数字(可能为 0)，然后是第 2 段中的数字，依此类推。所以，我们首先有一些蓝色差异，然后是红色差异，然后又是几个蓝色差异，然后又是红色差异等。

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

现在，每个蓝色的差异不超过1/k，因为被减数和减数来自同一个段。并且所有红色的差加起来(也就是它们的和!)不超过1。(暂时跳过其余部分，因为这是作业题。)

---

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