找到一个线性时间算法，对区间[0,2]中的n个数字进行排序，使得对于每2个数字a，b：|a-b| > (1/n)^2
找到一个线性时间算法，对区间[0,2]中的n个数字进行排序，使得对于每2个数字a，b：|a-b| > (1/n)^2
提问于 2013-02-13 20:26:56
我真的很感谢任何人的帮助。这是一个问题：
找到一个线性时间算法，对区间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进行排序就足够了，但我真的不知道如何做到这一点……
这真的很令人沮丧。:(
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-02-14 03:24:37
您附加的数字是从0到4n^2的整数。
如果你以2n为基数考虑这些，那么你就有两位数了。
您可以使用复杂度为O(nk)的radix sort对它们进行排序，其中k是位数。
在你的例子中是k=2，所以整个算法是O(2n)=O(n)，即线性。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14853562
复制相关文章
相似问题
腾讯云开发者
