如果有任何帮助，我将不胜感激。这是问题:
找到一个线性时间算法，对区间 [0,2] 中的 n 个数字进行排序，使得对于每 2 个数字 a,b :|a-b| > (1/n)^2
这里可悲的是，我阅读了这个问题的答案，但仍然不知道如何解决它......他们是这样说的:
对于每个数字 ai(假设 i 是索引)，我们将“附加”一个数字 ni，这样: ni/2n2 <= ai <= (ni+1)/2n2
(这正是他们的写法，我认为他们的意思是 ni/(2n^2) 和 (ni+1)/(2n^2) 但我不确定)。 然后他们说不难证明如何在线性时间内对数字 ni 进行排序...
我明白为什么足以说明如何在线性时间内对数字 ni 进行排序，但我真的不知道该怎么做...
这真是令人沮丧...:(
最佳答案
您附上了从 0 到 4n^2 的整数。
如果您以 2n 为基数考虑这些，那么您有 2 位数字。
您可以使用 radix sort 对这些进行排序其复杂度为 O(nk)，其中 k 是位数。
在你的情况下 k=2，所以整体算法是 O(2n)=O(n)，即线性。
关于algorithm - 找到一个线性时间算法，对区间 [0,2] 中的 n 个数字进行排序，使得对于每 2 个数字 a,b : |a-b| > (1/n)^2，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14853562/