归档 2015年2月4日

寻找数组第k大元素的线性时间选择算法

给定一个包含n个元素的数组,怎样从中找出第k大的数。

What is the most efficient algorithm to find the kth smallest element in an array having n elements?

此问题被称为求第k顺序统计量(kth order statistic)。

求解该问题的线性时间算法(既包括确定性算法,也包括非确定性算法)列举如下:

1. Quickselect (快速选择)

2. Median-of-medians (BFPRT) (中位数的中位数)

3. Introselect (内省选择)

4. Unnamed ...

继续阅读

昨天

明天

归档