前段时间面了蚂蚁一个技术还蛮强的团队,圈子比较小,所以在此不表。 二面面试官根据汇报层级推测应该是 P9 级别及以上，在美国电面我，面试风格偏硅谷那边。虽然感觉这道题面完自己没表现好，凉凉了，不过觉得还是蛮有意思，觉得自己思考问题还是不够严谨,有很大提高的空间，所以写出来总结。
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5
这道题目是 Leetcode 的 hard 难度的原题。求中位数或者 topK 的问题我们通常都会想用堆来解决。 但是面试官又进一步加大了难度，他要求内存使用很小，没有磁盘，但是压榨空间的同时可以忍受一定时间的损耗。且面试官不仅要求说出思路，要写出完整可经过大数据检测的 production code。
不考虑内存的方式就是 Leetcode 论坛上的题解。 基本思想是建立两个堆。左边是大根堆，右边是小根堆。 如果是奇数的时候，大根堆的堆顶是中位数。
例如：[1,2,3,4,5] 大根堆建立如下：
3
/ \
1 2
小根堆建立如下:
4
/
5
偶数的时候则是最大堆和最小堆顶的平均数。
例如: [1, 2, 3, 4]
大根堆建立如下：
2
/
1
小根堆建立如下:
3
/
4
然后再维护一个奇数偶数的状态即可求中位数。
public class MedianStream {
private PriorityQueue<Integer> leftHeap = new PriorityQueue<>(5, Collections.reverseOrder());
private PriorityQueue<Integer> rightHeap = new PriorityQueue<>(5);
private boolean even = true;
public double getMedian() {
if (even) {
return (leftHeap.peek() + rightHeap.peek()) / 2.0;
} else {
return leftHeap.peek();
}
}
public void addNum(int num) {
if (even) {
rightHeap.offer(num);
int rightMin = rightHeap.poll();
leftHeap.offer(rightMin);
} else {
leftHeap.offer(num);
int leftMax = leftHeap.poll();
rightHeap.offer(leftMax);
}
System.out.println(leftHeap);
System.out.println(rightHeap);
// 奇偶变换.
even = !even;
}
}
但是这样做的问题就是可能内存会爆掉。如果你的流无限大，那么意味着这些数据都要存在内存中，堆必须要能够建无限大。如果内存必须很小的方式，用时间换空间。
public class Median {
private static int BUCKET_SIZE = 1000;
private int left = 0;
private int right = Integer.MAX_VALUE;
// 流这里用 int[] 代替
public double findMedian(int[] nums) {
// 第一遍读取 stream 将问题复杂度转化为内存可接受的量级.
int[] bucket = new int[BUCKET_SIZE];
int step = (right - left) / BUCKET_SIZE;
boolean even = true;
int sumCount = 0;
for (int i = 0; i < nums.length; i++) {
int index = nums[i] / step;
bucket[index] = bucket[index] + 1;
sumCount++;
even = !even;
}
// 如果是偶数,那么就需要计算第 topK 个数
// 如果是奇数, 那么需要计算第 topK 和 topK+1 的个数.
int topK = even ? sumCount / 2 : sumCount / 2 + 1;
int index = 0;
int indexBucketCount = 0;
for (index = 0; index < bucket.length; index++) {
indexBucketCount = bucket[index];
if (indexBucketCount >= topK) {
// 当前 bucket 就是中位数的 bucket.
break;
}
topK -= indexBucketCount;
}
// 划分到这里其实转化为一个 topK 的问题, 再读一遍流.
if (even && indexBucketCount == topK) {
left = index * step;
right = (index + 2) * step;
return helperEven(nums, topK);
// 偶数的时候, 恰好划分到在左右两个子段中.
// 左右两段中 [topIndex-K + (topIndex-K + 1)] / 2.
} else if (even) {
left = index * step;
right = (index + 1) * step;
return helperEven(nums, topK);
// 左边 [topIndex-K + (topIndex-K + 1)] / 2
} else {
left = index * step;
right = (index + 1) * step;
return helperOdd(nums, topK);
// 奇数, 左边 topIndex-K
}
}
}
这里边界条件我们处理好之后,关键还是 helperOdd 和 helperEven 这两个函数怎么去求 topK 的问题. 我们还是转化为一个 topK 的问题,那么求 top-K 和 top(K+1)的问题到这里我们是不是可以用堆来解决了呢? 答案是不能,考虑极端情况。 中位数的重复次数非常多
eg:
[100,100,100,100,100...] (1000 亿个 100)
你的划分恰好落到这个桶里面,内存同样会爆掉。
假如我们的划分 bucket 大小是 10000,那么最大的时候区间就是 20000。(对应上面的偶数且落到两个分桶的情况) 那么既然划分到某一个 bucket 了,我们直接用数数字的方式来求 topK 就可以了。 我们选用 TreeMap 这种数据结构计数。然后分奇数偶数去求解。
private double helperEven(int[] nums, int topK) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= left && nums[i] <= right) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], 1);
} else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}
}
int count = 0;
int kNum = Integer.MIN_VALUE;
int kNextNum = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int currentCountIndex = entry.getValue();
if (kNum != Integer.MIN_VALUE) {
kNextNum = entry.getKey();
break;
}
if (count + currentCountIndex == topK) {
kNum = entry.getKey();
} else if (count + currentCountIndex > topK) {
kNum = entry.getKey();
kNextNum = entry.getKey();
break;
} else {
count += currentCountIndex;
}
}
return (kNum + kNextNum) / 2.0;
}
private double helperOdd(int[] nums, int topK) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= left && nums[i] <= right) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], 1);
} else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}
}
int count = 0;
int kNum = Integer.MIN_VALUE;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int currentCountIndex = entry.getValue();
if (currentCountIndex + count >= topK) {
kNum = entry.getKey();
break;
} else {
count += currentCountIndex;
}
}
return kNum;
}
至此,我觉得算是一个比较好的解决方案，leetcode 社区没有相关的解答和探索，欢迎大家交流。
这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.