本人的一个作业题，实在想不出，想请大侠指点

设有一个算法Median能在O(n)的时间内计算一个数组的中位值(即将数组的元素按大小顺序排列正好位于中间的值)。给定一个有n个元素的数组，能否以Median算法为基础设计一个算法，对任意的整数1≤i≤n，该算法在O(n)的时间内求出数组中第i大小的元素。如果能，请给出一个这样的算法并分析其最坏时间复杂性。

12 个解决方案

#1

这里有一个参考 

类型4．一般性选择问题 
输入：数组L, L的长度n, 正整数k, 1≤ k≤ n. 
输出：第k小的数 
通常算法 
1．排序 
2．找第k小的数 
时间复杂性：O(nlogn) 

算法4 Select(S,k) 改进的算法 
1．将S划分成5个一组， 共nM= [n/5] 个组 
2．每组找中位数，nM个中位数放到集合M 
3．m*←Select(M, |M|/2 ) 将S中的数划分成A,B,C,D四个集合 
4．把A和D中的每个元素与m*比较，小的构成S1, 大的构成S2 
5．S1←S1∪C; S2←S2∪B 
6．if k =|S1|+1 then 输出m* 
7．else if k≤|S1| 
8． then Select(S1,k) 
9. else Select(S2,k-|S1|-1) 

复杂性估计 更详细的请参考王晓东的《计算机算法设计与分析》（第2版） 电子工业出版社 P24-26 

复杂性：W(n)=O(n) 
行2： O(n) 
行3： W(n/5) 
行4： O(n) 
行8-9: O(n) 

#2

...

#3

up..

#4

mark

#5

up过

#6

mark

#7

支持一下

#8

mark

#9

汗

up下

#10

1楼正解

#11

good

#12

友情 up