参考答案

内存足够的情况： 可以使⽤用类似quick sort的思想进行，均摊复杂度为O(n)，算法思想如下：
• 随机选取一个元素，将比它小的元素放在它左边，比它大的元素放在右边
• 如果它恰好在中位数的位置，那么它就是中位数，可以直接返回
• 如果小于它的数超过一半，那么中位数一定在左半边，递归到左边处理
• 否则，中位数一定在右半边，根据左半边的元素个数计算出中位数是右半边的第几大，然后递归 到右半边处理
内存不⾜足的情况：
方法⼀：⼆分法
思路：一个重要的线索是，这些数都是整数。整数就有范围了，32位系统中就是[-2^32, 2^32- 1]， 有了范围我们就可以对这个范围进行二分，然后找有多少个数⼩于Mid,多少数大于mid，然后递归， 和基于quicksort思想的第k大⽅方法类似
方法二：分桶法 思路：化大为小，把所有数划分到各个小区间，把每个数映射到对应的区间⾥里，对每个区间中数的 个数进行计数，数一遍各个区间，看看中位数落在哪个区间，若够小，使⽤用基于内存的算法，否则 继续划分