0 0 投票数

### 题目描述

[2,3,4] 的中位数是 $3$

[2,3] 的中位数是 $(2 + 3) / 2 = 2.5$

void addNum(int num) – 从数据流中添加一个整数到数据结构中。
double findMedian() – 返回目前所有元素的中位数。

### 样例

addNum(1)
findMedian() -> 1.5
findMedian() -> 2

### 题解

if (max.size() == min.size()) {
// n 是偶数
return 0.5 * (max.peek() + min.peek());
} else {
// n 是奇数
return max.peek();
}

if (num < max.peek()) {
} else {
}

while (true) {
int minSize = min.size();
int maxSize = max.size();
if (minSize == maxSize || minSize + 1 == maxSize) {
break;
} else {
if (minSize < maxSize) {
} else {
}
}
}

findMedian() 中，我们可以很自信地说出，这样的情况不可能存在。

public double findMedian() {
assert !max.isEmpty();
if (max.size() == min.size()) {
return 0.5 * (max.peek() + min.peek());
} else {
return max.peek();
}
}

if (max.isEmpty() || num < max.peek()) {}

### 完整代码

class MedianFinder {

private static PriorityQueue<Integer> min;
private static PriorityQueue<Integer> max;

public MedianFinder() {
min = new PriorityQueue<>();
max = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
}

public void addNum(int num) {
if (max.isEmpty() || num < max.peek()) {
} else {
}
while (true) {
int minSize = min.size();
int maxSize = max.size();
if (minSize == maxSize || minSize + 1 == maxSize) {
break;
} else {
if (minSize < maxSize) {
} else {
}
}
}
}

public double findMedian() {
assert !max.isEmpty();
if (max.size() == min.size()) {
return 0.5 * (max.peek() + min.peek());
} else {
return max.peek();
}
}
}

### 备注

if (pq.size() % 2 == 0) {
return 0.5 * (pq.get(pq.size()) + pq.get(pq.size() + 1));
} else {
return pq.get(pq.size() / 2);
}

0 0 投票数