1. PTT
  2. Prob_Solve

[问题] Sorting in O(n)...

楼主: shaopin (Brian)   2014-10-27 13:35:39
今天看CLRS 看到一题 Problem
假设在一个圆里面 均匀分布著 n 个点
目标是要依照每个点对(0,0)的距离排序
每个点都是(x,y) x^2+y^2 <=1
题目要求O(n) 原文中有 hint 只是还没时间想出来
请问这和有没有均匀分布有什么关系?
作者: freef1y3 ( )   2014-10-27 16:03:00
若没有均匀分布，所有点都在 x 轴上，就变成排序 N 个数这样就不可能 O(N) 了，所以可能跟均匀分布有关吧只是均匀分布有没有更精确的定义呢
作者: flere (人间失格)   2014-10-27 19:41:00
听过类似的, 我想应该是bucket sort吧
作者: FRAXIS (喔喔)   2014-10-27 21:59:00
你要了解uniform distribution in disk的概念..http://mathworld.wolfram.com/DiskPointPicking.html然后就可以设计bucket了..
继续阅读
[问题] selection problemjb679123[问题] 不重叠的圆求最大面积jjwang[问题] 时间复杂度qwerty147852Re: [问题] 给定n个排好序的整数阵列 找中位数FRAXISRe: [问题] 给定n个排好序的整数阵列 找中位数DJWSRe: [问题] 给定n个排好序的整数阵列 找中位数chzRe: [问题] 给定n个排好序的整数阵列 找中位数dreamoonRe: [问题] 给定n个排好序的整数阵列 找中位数DJWSRe: [问题] 给定n个排好序的整数阵列 找中位数FRAXISRe: [问题] 给定n个排好序的整数阵列 找中位数DJWS

Links booklink

Contact Us: admin [ a t ] ucptt.com