y*****e
发帖数: 712 | 1 很多家都有这题，假如有很多points，找出离原点最近的k个点。
做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点，还有
insert/pop operation的complexity是（n-k）log(k), 综合下来是nlogk
另外一种方法是任意去pivot, 每次call partition function, 把数组按放到pivot的
左边和右边，一直到pivot = k为止，直接return pivot左边的所有点。这种做法应该
是每次去掉一半的数组
n + n/2 + n/4 +.... = 2n也就是o(n),
应该是selection sort更好啊，为啥面试官总是让写heap? 是不是有其他的考量？比如
是streaming data或者数据量太大，不能一次完全放到array里？ |
j********l
发帖数: 325 | 2 这两种方法各有优缺点，如果数据量真的太大，内存hold不住的话，maxheap不存在这
个问题，但方法二不行。。。
如果强行使用方法二的话，需要使用divide and conquer，估计这就是一道系统设计
题了 |
c******n
发帖数: 4965 | 3 一般是要求不断地往里加点， heap/insertion 可以， partition 不行
【在 y*****e 的大作中提到】
: 很多家都有这题，假如有很多points，找出离原点最近的k个点。
: 做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点，还有
: insert/pop operation的complexity是（n-k）log(k), 综合下来是nlogk
: 另外一种方法是任意去pivot, 每次call partition function, 把数组按放到pivot的
: 左边和右边，一直到pivot = k为止，直接return pivot左边的所有点。这种做法应该
: 是每次去掉一半的数组
: n + n/2 + n/4 +.... = 2n也就是o(n),
: 应该是selection sort更好啊，为啥面试官总是让写heap? 是不是有其他的考量？比如
: 是streaming data或者数据量太大，不能一次完全放到array里？
|
x******8
发帖数: 48 | 4 快速排序也可以，follow up 数据很大或者数据是stream的 |
P******r
发帖数: 1342 | 5 你pivot怎么选？每次去掉一半是最优状况。最差状况每次只能去掉一个吧。
：很多家都有这题，假如有很多points，找出离原点最近的k个点。
：做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点，还有 |
h****3
发帖数: 89 | 6 这个问题很好，感觉一改改就变系统设计了
我觉得楼上几位分析的很对，如果你有海量数据，维持k个固定space应该会更优；但如
果数据量有限，selection sort会更好 |
g******n
发帖数: 10 | 7 你的第二种方法最坏情况下时间复杂度是 O(n^2)，不是 O(n)，因为不是每次都刚好把
数组分成长度相当的两半，最坏情况下两边长度分别是 0 和 n-1，所以 T(n) = T(n-1
) + O(n)，总的时间复杂度是 O(n^2). 另外这种方法也不叫 selection sort，而是
叫做 randomized-select，因为过程跟 randomized-quicksort 的 partition 非常相
似，期望时间复杂度是 O(n)。详细内容可以看 CLRS pp. 215, §9.2
Selection in expected linear time |
y*****e
发帖数: 712 | 8 谢谢，我得把CLRS拿出来看看啦
-1
【在 g******n 的大作中提到】
: 你的第二种方法最坏情况下时间复杂度是 O(n^2)，不是 O(n)，因为不是每次都刚好把
: 数组分成长度相当的两半，最坏情况下两边长度分别是 0 和 n-1，所以 T(n) = T(n-1
: ) + O(n)，总的时间复杂度是 O(n^2). 另外这种方法也不叫 selection sort，而是
: 叫做 randomized-select，因为过程跟 randomized-quicksort 的 partition 非常相
: 似，期望时间复杂度是 O(n)。详细内容可以看 CLRS pp. 215, §9.2
: Selection in expected linear time
|
c******w
发帖数: 1108 | 9 数据分5个5个的partition，然后pivot用median of medians来选就好了。textbook
material。
【在 P******r 的大作中提到】
: 你pivot怎么选？每次去掉一半是最优状况。最差状况每次只能去掉一个吧。
:
: ：很多家都有这题，假如有很多points，找出离原点最近的k个点。
: ：做法就是建个size为k的heap, 建heap的complexity是o(k), 对后面n - k的点，还有
|
n******n
发帖数: 12088 | 10 方法2也可以。维护一个大小为2K的缓存，在里面做选择。
【在 j********l 的大作中提到】
: 这两种方法各有优缺点，如果数据量真的太大，内存hold不住的话，maxheap不存在这
: 个问题，但方法二不行。。。
: 如果强行使用方法二的话，需要使用divide and conquer，估计这就是一道系统设计
: 题了
|
n******n
发帖数: 12088 | 11 快排最坏也是平方。这里回答平均复杂度够了
-1
【在 g******n 的大作中提到】
: 你的第二种方法最坏情况下时间复杂度是 O(n^2)，不是 O(n)，因为不是每次都刚好把
: 数组分成长度相当的两半，最坏情况下两边长度分别是 0 和 n-1，所以 T(n) = T(n-1
: ) + O(n)，总的时间复杂度是 O(n^2). 另外这种方法也不叫 selection sort，而是
: 叫做 randomized-select，因为过程跟 randomized-quicksort 的 partition 非常相
: 似，期望时间复杂度是 O(n)。详细内容可以看 CLRS pp. 215, §9.2
: Selection in expected linear time
|
