Question

怎么在O（N）时间内求一个无序数组的中位数

关键是在O（N）时间复杂度内，要求一个无序数组里的中位数，求助!!!

Answer 1

用改进的快排吧，每次看选定的标定数是在左半还是右半，然后根据要求对剩下的进行排序，比如说一共10个数，第一次标定的数排在了第3位，那么你只要拍剩3右边的数就好了，中位数肯定在右边，这个理论上的期望是o（n），或者用桶排序，排序复杂度就是o(n);再找出中位数就好了。

Answer 2

可以先在O（N）内排序，然后用中位索引取值，计数排序就是O（N）的，用这个就成。