作者shaopin (problem maker)
看板Prob_Solve
标题[问题] Sorting in O(n)...
时间Mon Oct 27 13:35:39 2014
今天看CLRS 看到一题 Problem
假设在一个圆里面 均匀分布着 n 个点
目标是要依照每个点对(0,0)的距离排序
每个点都是(x,y) x^2+y^2 <=1
题目要求O(n) 原文中有 hint 只是还没时间想出来
请问这和有没有均匀分布有什麽关系?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 99.57.137.146
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1414388141.A.2D0.html
1F：→ freef1y3: 若没有均匀分布，所有点都在 x 轴上，就变成排序 N 个数 10/27 16:03
2F：→ freef1y3: 这样就不可能 O(N) 了，所以可能跟均匀分布有关吧 10/27 16:03
3F：→ freef1y3: 只是均匀分布有没有更精确的定义呢 10/27 16:07
4F：推 flere: 听过类似的, 我想应该是bucket sort吧 10/27 19:41
5F：推 FRAXIS: 你要了解uniform distribution in disk的概念.. 10/27 21:59
7F：→ FRAXIS: 然後就可以设计bucket了.. 10/27 22:00