计算机算法(Ｃ＋＋版)上的一道题 （高分）
设Ｓ为一个有ｎ个关键字的序列(不必排序).若|{a属于Ｓ:a <b}|> =n/4,并且|{a属于S:a> b}| <=n/4 则称关键字b为Ｓ的近似中值。设计一个时间为O(n)的算法查找Ｓ的近似中值.
初学算法，请各位高手指点！
[解决办法]
满足条件的近似中值不止一个吧，应该是一个集合。首先，对于一个序列，我们可以在O(n)的时间里面找到他排序后的第k个元素s，并且将这个序列分成两个部分,前一部分小于s，后一部分大于s（你可以google select algorithm or partial sort)。那么对于lz的问题，现对S求第n/4个元素，然后去掉前n/4的元素得到S '，然后对S '求第n '/3个元素，S '的前半部分即为所求。
ps 你可能要了解select算法才能看懂这个，另外，这里的边界可能并不准确，但是大体上是这样的
[解决办法]
支持楼上的，类似中数查找算法。
[解决办法]
是的，找p分数本身就是O(n)的算法
