如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
数据范围：数据流中数个数满足 
，大小满足 
进阶： 空间复杂度%20%5C)
， 时间复杂度 %20%5C)
进阶： 空间复杂度
[编程题]数据流中的中位数
#Python版 #该题Python版牛客有问题 #一直提示 def GetMedian(self)函数多给了一个参数 ，然后自己def GetMedian(self,n=None): #多给它加了一个默认参数，就过了。。。我擦 #思路：两个堆，自己实现，一个最大堆，一个最小堆
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.minNums=[]
self.maxNums=[]
def maxHeapInsert(self,num):
self.maxNums.append(num)
lens = len(self.maxNums)
i = lens - 1
while i > 0:
if self.maxNums[i] > self.maxNums[(i - 1) / 2]:
t = self.maxNums[(i - 1) / 2]
self.maxNums[(i - 1) / 2] = self.maxNums[i]
self.maxNums[i] = t
i = (i - 1) / 2
else:
break
def maxHeapPop(self):
t = self.maxNums[0]
self.maxNums[0] = self.maxNums[-1]
self.maxNums.pop()
lens = len(self.maxNums)
i = 0
while 2 * i + 1 < lens:
nexti = 2 * i + 1
if (nexti + 1 < lens) and self.maxNums[nexti + 1] > self.maxNums[nexti]:
nexti += 1
if self.maxNums[nexti] > self.maxNums[i]:
tmp = self.maxNums[i]
self.maxNums[i] = self.maxNums[nexti]
self.maxNums[nexti] = tmp
i = nexti
else:
break
return t
def minHeapInsert(self,num):
self.minNums.append(num)
lens = len(self.minNums)
i = lens - 1
while i > 0:
if self.minNums[i] < self.minNums[(i - 1) / 2]:
t = self.minNums[(i - 1) / 2]
self.minNums[(i - 1) / 2] = self.minNums[i]
self.minNums[i] = t
i = (i - 1) / 2
else:
break
def minHeapPop(self):
t = self.minNums[0]
self.minNums[0] = self.minNums[-1]
self.minNums.pop()
lens = len(self.minNums)
i = 0
while 2 * i + 1 < lens:
nexti = 2 * i + 1
if (nexti + 1 < lens) and self.minNums[nexti + 1] < self.minNums[nexti]:
nexti += 1
if self.minNums[nexti] < self.minNums[i]:
tmp = self.minNums[i]
self.minNums[i] = self.minNums[nexti]
self.minNums[nexti] = tmp
i = nexti
else:
break
return t
def Insert(self, num):
if (len(self.minNums)+len(self.maxNums))&1==0:
if len(self.maxNums)>0 and num < self.maxNums[0]:
self.maxHeapInsert(num)
num = self.maxHeapPop()
self.minHeapInsert(num)
else:
if len(self.minNums)>0 and num > self.minNums[0]:
self.minHeapInsert(num)
num = self.minHeapPop()
self.maxHeapInsert(num)
def GetMedian(self,n=None):
allLen = len(self.minNums) + len(self.maxNums)
if allLen ==0:
return -1
if allLen &1==1:
return self.minNums[0]
else:
return (self.maxNums[0] + self.minNums[0]+0.0)/2
t = Solution()
t.Insert(5)
print t.GetMedian()
t.Insert(2)
print t.GetMedian()
t.Insert(3)
print t.GetMedian()
t.Insert(4)
print t.GetMedian()
t.Insert(1)
print t.GetMedian()
t.Insert(6)
print t.GetMedian()
t.Insert(7)
print t.GetMedian()
t.Insert(0)
print t.GetMedian()
t.Insert(8)
print t.GetMedian()
发表于 2016-12-09 16:46:56
回复(5)
解题思路就是用两个堆，一个大顶堆，一个小顶堆来过滤数据。
自己实现的堆类。
public class Solution{
private Heap maxHeap = new Heap(Heap.isMaxHeap);
private Heap minHeap = new Heap(Heap.isMinHeap);
/**
* 插入有两种思路：
* 1：直接插入大堆中，之后若两堆尺寸之差大于1(也就是2)，则从大堆中弹出堆顶元素并插入到小堆中
* 若两队之差不大于1，则直接插入大堆中即可。
* 2：奇数个数插入到大堆中，偶数个数插入到小堆中，
* 但是 可能会出现当前待插入的数比小堆堆顶元素大，此时需要将元素先插入到小堆，然后将小堆堆顶元素弹出并插入到大堆中
* 对于偶数时插入小堆的情况，一样的道理。why?
* 因为要保证最大堆的元素要比最小堆的元素都要小。
* @param num
*/
public void Insert(Integer num) {
//若总尺寸为偶数，则插入大顶堆中
if(((maxHeap.si敏感词Heap.size()) & 1) == 0){
if(minHeap.size() != 0 && num > minHeap.peek()){
minHeap.add(num);
maxHeap.add(minHeap.pop());
}else{
maxHeap.add(num);
}
}else{
if(maxHeap.size() != 0 && num < maxHeap.peek()){
maxHeap.add(num);
minHeap.add(maxHeap.pop());
}else{
minHeap.add(num);
}
}
}
public Double GetMedian() {
double res = 0.0;
if(((maxHeap.si敏感词Heap.size()) & 1) == 0){
res = (maxHeap.peek() + minHeap.peek()) / 2.0;
}else{
res = maxHeap.peek();
}
return res;
}
}
//堆类，可直接设置最大堆最小堆
class Heap {
public List<Integer> list = null;
public static final boolean isMaxHeap = true;
public static final boolean isMinHeap = false;
private boolean flag = true; //true表示最大堆，false表示最小堆
public Heap(){
this.list = new ArrayList<Integer>();
}
public Heap(boolean flag){
this.list = new ArrayList<Integer>();
this.flag = flag;
}
//获取堆大小
public int size(){
return this.list.size();
}
//获取堆顶元素
public int peek(){
if(list.size() == 0) return 0;
return list.get(0);
}
//插入元素，从插入点开始向上调整堆
public void add(int val){
this.list.add(val);
int i = list.size() - 1, index, parent, cur;
while(i > 0){
index = (i - 1) / 2;
parent = list.get(index);
cur = list.get(i);
if(flag == true && parent < cur){
swap(index, i);
}else if(flag == false && parent > cur){
swap(index, i);
}
i = index;
}
}
/**
* 将堆顶元素取出,并重新调整堆。
* 1>取出堆顶元素
* 2>将最后一个元素放到堆顶
* 3>向下调整堆
*/
public int pop(){
if(list.size() == 0) return -1;
int res = list.get(0);
list.set(0,list.get(list.size() - 1));
list.remove(list.size()-1);
int len = list.size() - 1 , i = 0;
int left , right;
while(i < len){
left = (i << 1) + 1;
right= (i << 1) + 2;
int maxIndex = i;
if(flag == true){
if(left < len && list.get(left) > list.get(maxIndex)) maxIndex = left;
if(right< len && list.get(right)> list.get(maxIndex)) maxIndex = right;
}else{
if(left < len && list.get(left) < list.get(maxIndex)) maxIndex = left;
if(right< len && list.get(right)< list.get(maxIndex)) maxIndex = right;
}
if(maxIndex != i){
swap(maxIndex,i);
i = maxIndex;
}else break;
}
return res;
}
//交换list中两个位置的元素
public void swap(int i, int j){
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j,temp);
}
}
编辑于 2015-10-05 21:15:09
回复(13)
PYTHON
- 大根堆：large保存大的半数的数据
- 小根堆：small保存小的半数的数据
获取中位数的时间复杂度为O（1），插入一个数据的时间复杂度为O（log(n)）
技巧：
- 构造小根堆时，对数组元素取负值来构造
- heappush(heap,data),将deat放入大根堆中
- heapposh(heap),弹出heap中的最小值
- heappushpop(heap,data),将data放入大根堆中，再弹出堆heap的最小值
# -*- coding:utf-8 -*- from heapq import * class Solution: def __init__(self): self.heaps = [], [] def Insert(self, num): # write code here small, large = self.heaps heappush(small, -heappushpop(large, num))#将num放入大根堆，并弹出大根堆的最小值，取反，放入大根堆small if len(large) < len(small): heappush(large, -heappop(small)) #弹出small中最小的值，取反，即最大的值，放入large def GetMedian(self,ss): # write code here small,large = self.heaps if len(large) > len(small): return float(large[0]) return (large[0] - small[0]) /2.0
发表于 2018-08-19 15:11:47
回复(6)
mark版的详细解释（c++）
class Solution {
public:
void Insert(int num)
{
if(left.empty() || num <= left.top()){
left.push(num);
}else{
right.push(num);
}
// 左边大顶堆的大小最多可以比右边小顶堆大1（奇数次输入）
if(left.size() == right.size() + 2){
right.push(left.top());
left.pop();
}
// 因为最后返回的只有可能是左边大顶堆的堆顶，所以右边小顶堆的大小不能比左边小顶堆大
if(left.size() + 1 == right.size()){
left.push(right.top());
right.pop();
}
}
double GetMedian()
{
return left.size() == right.size() ? (left.top() + right.top())/2\. : left.top();
}
private:
// 右边小顶堆的元素都大于左边大顶堆的元素，并且左边元素的个数，要么与右边相等（偶数次输入），要么比右边大1（奇数次输入）
priority_queue, less > left; // 大顶堆
priority_queue, greater > right; // 小顶堆
};最大堆和最小堆的底层实现
class Solution {
private:
vector<int> max_heap;
vector<int> min_heap;
void adjust_heap(vector<int> &nums, int lo, int hi, bool is_max) {
for (int cur = lo, next = cur * 2 + 1; next <= hi; cur = next, next = cur * 2 + 1) {
if (is_max) {
if (next < hi && nums[next + 1] > nums[next]) {
++next;
}
if (nums[next] > nums[cur]) {
swap(nums[next], nums[cur]);
} else {
break;
}
} else {
if (next < hi && nums[next + 1] < nums[next]) {
++next;
}
if (nums[next] < nums[cur]) {
swap(nums[next], nums[cur]);
} else {
break;
}
}
}
}
void build_heap(vector<int> &heap, bool is_max) {
int n = heap.size();
for (int i = n / 2 - 1; i >= 0; --i) {
adjust_heap(heap, i, n - 1, is_max);
}
}
int pop(vector<int> &heap, bool is_max) {
int ret = heap[0];
heap.erase(heap.begin());
build_heap(heap, is_max);
return ret;
}
void push(vector<int> &heap, int num, bool is_max) {
heap.emplace_back(num);
build_heap(heap, is_max);
}
public:
void Insert(int num) {
if (min_heap.empty() || num > min_heap[0]) {
push(min_heap, num, false);
} else {
push(max_heap, num, true);
}
if (min_heap.size() == max_heap.size() + 2) {
push(max_heap, pop(min_heap, false), true);
}
if (min_heap.size() + 1 == max_heap.size()) {
push(min_heap, pop(max_heap, true), false);
}
}
double GetMedian() {
return min_heap.size() == max_heap.si***_heap[0] + max_heap[0]) / 2. : min_heap[0];
}
};
编辑于 2019-04-18 00:31:33
回复(4)
/**
@author zhengyanan
@date 2017/3/9 @time 16:26
version_2:
核心思路：
1.维护一个大顶堆，一个小顶堆，且保证两点：
1）小顶堆里的全大于 大顶堆里的；
2）2个堆个数的差值小于等于1
2.当insert的数字个数为奇数时：使小顶堆个数比大顶堆多1；
当insert的数字个数为偶数时，使大顶堆个数跟小顶堆个数一样。
3.那么当总数字个数为奇数时，中位数就是小顶堆堆头；
当总数字个数为偶数时，中卫数就是 2个堆堆头平均数
运行时间：43ms
占用内存：699k
*/
private PriorityQueue<Integer> min = new PriorityQueue<Integer>();
private PriorityQueue<Integer> max = new PriorityQueue<Integer>(15,new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
private int count = 0;
public void Insert(Integer num) {
count++;
if (count % 2 == 1){
max.offer(num);//先从大顶堆过滤一遍
min.offer(max.poll());
}else {
min.offer(num);//先从小顶堆过滤一遍
max.offer(min.poll());
}
}
public Double GetMedian() {
if (count % 2 == 0) return (min.peek() + max.peek())/2.0;
else return (double)min.peek();
}
/**
@author zhengyanan
@date 2017/3/9 @time 16:08
version_1:
核心思路：
1.直接维护一个链表，每次加入时，用直接插入的思想，放置在合适的位置。
*/
// LinkedList<Integer> data = new LinkedList<Integer>();
// public void Insert(Integer num) {
// for (int i = data.size() - 1; i >= 0 ; i--) {
// if (num >= data.get(i)){
// data.add(i+1,num);
// return;
// }
// }
// data.addFirst(num);
// }
//
// public Double GetMedian() {
// int size = data.size();
// if (size% 2 == 1) return (double)data.get(size/2);
// else return (data.get(size/2) + data.get(size/2 - 1))/2.0;
// }
发表于 2017-03-09 16:53:36
回复(3)
import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
// smaller堆用于存放相对较小的一半数字，larger堆用于存放相对较大的一半数字
// 由于默认排序堆顶是最小值，而对于smaller的一半我们更关注最大值，因此使用reverseOrder()来初始化
private PriorityQueue<Integer> smaller = new PriorityQueue<>(Collections.reverseOrder());
private PriorityQueue<Integer> larger = new PriorityQueue<>();
public void Insert(Integer num) {
// 首次将数字存入smaller，然后在将smaller中堆顶的（较小一半数字的最大值）存入larger
smaller.add(num);
larger.add(smaller.poll());
// 为了保证larger内的数量<=smaller内的数量，进行两个堆大小的比较，并进行转移
// 此规则下，如果两个堆数量相等，则中位数为两个堆顶数字的平均值；若不相等则为smaller的堆顶数字
// 也可以使larger存储更多数字，则不相等时，中位数为larger的堆顶数字
if (larger.size() > smaller.size()) {
smaller.add(larger.poll());
}
}
public Double GetMedian() {
// 如前所述，两者大小相等，则求平均
if (smaller.size() == larger.size()) {
return ((double)smaller.peek() + (double)larger.peek()) / 2;
} else { // 否则中位数为smaller的堆顶数字
return (double)smaller.peek();
}
}
}
编辑于 2018-07-12 23:17:37
回复(0)
//看大家都用堆，那我来个树，插入和取中值复杂度都是lgn
public class Solution {
private TreeNode root;
public void Insert(Integer num) {
root = Insert(root, num);
}
private TreeNode Insert(TreeNode node, Integer num){
if(node == null)
return new TreeNode(num, 1);
node.size++;
if(num <= node.val)
node.left = Insert(node.left, num);
else
node.right = Insert(node.right, num);
return node;
}
public Double GetMedian() {
if(root == null)
return null;
if((root.size & 1) == 0)
return (double)(getKth(root, root.size/2) + getKth(root, root.size/2 + 1))/2;
else
return (double)getKth(root, (root.size + 1)/2);
}
private int getKth(TreeNode node, int k){
int size = node.left == null ? 0 : node.left.size;
if(k <= size)
return getKth(node.left, k);
else if(k == size + 1)
return node.val;
else
return getKth(node.right, k-size-1);
}
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
int size = 0;//该字段的含义是以该节点为子树根的节点总个数
public TreeNode(int val, int size) {
this.val = val;
this.size = size;
}
}
}
编辑于 2017-10-02 19:43:48
回复(1)
import java.util.*;
public class Solution {
// 代表排序后的左半部分
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
// 代表排序后的右半部分
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 时间复杂度O(logn)
public void Insert(Integer num) {
// 平均分配，元素个数为奇数时插入到maxHeap，为偶数时插入到minHeap
if ((minHeap.size() + maxHeap.size()) % 2 == 1) {
// 若num完全小于minHeap的所有元素，直接将num插入maxHeap即可
// 若num大于minHeap中的一些元素，则将num插入minHeap, 然后移除minHeap的最小值，将其插入maxHeap
if (!minHeap.isEmpty() && num > minHeap.element()) {
minHeap.add(num);
num = minHeap.remove();
}
maxHeap.add(num);
} else {
// 若num完全大于maxHeap的所有元素，直接将num插入minHeap即可
// 若num小于maxHeap中的一些元素，则将num插入maxHeap，然后移除maxHeap的最大值，将其插入minHeap
if (!maxHeap.isEmpty() && num < maxHeap.element()) {
maxHeap.add(num);
num = maxHeap.remove();
}
minHeap.add(num);
}
}
// 时间复杂度O(1)
public Double GetMedian() {
int size = maxHeap.size() + minHeap.size();
if (size % 2 == 1) {
return minHeap.element() * 1.0;
} else {
return (maxHeap.element() + minHeap.element()) / 2.0;
}
}
}
发表于 2021-09-16 11:55:57
回复(0)
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
// 初始化一个大根堆，存中位数左边的数据，一个小根堆，存中位数右边的数据
// 动态维护两个数据结构的大小，即最多只相差一个
// 因为要求的是中位数，那么这两个堆，大顶堆用来存较小的数，从大到小排列；
// 小顶堆存较大的数，从小到大的顺序排序*，显然中位数就是大顶堆的根节点与小顶堆的根节点和的平均数。
// 保证：小顶堆中的元素都大于等于大顶堆中的元素，所以每次塞值，并不是直接塞进去，而是从另一个堆中poll出一个最大（最小）的塞值
// 当数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中；
// 当数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中；
// 取中位数的时候，如果当前个数为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当前个数为奇数，显然是取小顶堆的根节点
// 小顶堆
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
// 大顶堆
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
// 记录偶数个还是奇数个
int count = 0;
// 每次插入小顶堆的是当前大顶堆中最大的数
// 每次插入大顶堆的是当前小顶堆中最小的数
// 这样保证小顶堆中的数永远大于等于大顶堆中的数
// 中位数就可以方便地从两者的根结点中获取了
public void Insert(Integer num) {
// 个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中
if (count % 2 == 0) {
maxHeap.offer(num);
int max = maxHeap.poll();
minHeap.offer(max);
} else {
// 个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中
minHeap.offer(num);
int min = minHeap.poll();
maxHeap.offer(min);
}
count++;
}
public Double GetMedian() {
// 当前为偶数个，则取小顶堆和大顶堆的堆顶元素求平均
if (count % 2 == 0) {
return new Double(minHeap.peek() + maxHeap.peek()) / 2;
} else {
// 当前为奇数个，则直接从小顶堆中取元素即可
return new Double(minHeap.peek());
}
}
}
发表于 2021-01-13 10:21:07
回复(0)
//非常有幸成为python的第一个完成这道题的人，
//但是我仍然忍不住想要吐槽
//给定的方法GetMedian（）并不需要入参，而这个地方却莫名其妙给了个入参，但是给定的函数中却没有说明。我试了老半天才试出来。希望管理员能及时处理一下
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.numbers = []
self.last = 0
self.new = 0
def Insert(self, num):
# write code here
if not self.numbers:
self.numbers.append(num)
self.last = num
else:
for i in range(len(self.numbers)):
if self.numbers[i] > num:
self.numbers.insert(i, num)
break
else:
self.numbers.append(num)
self.new = num
def GetMedian(self, x):
# write code here
if len(self.numbers) == 1:
self.last = self.numbers[0]
return self.numbers[0]
elif len(self.numbers) % 2 == 0:
last_pos = self.numbers.index(self.last)
if self.new >= self.last:
return (self.last + self.numbers[last_pos + 1]) / 2.0
elif self.new < self.last:
mid = (self.last + self.numbers[last_pos - 1]) / 2.0
self.last = self.numbers[last_pos - 1]
return mid
elif len(self.numbers) % 2 == 1:
last_pos = self.numbers.index(self.last)
if self.new >= self.last:
mid = self.numbers[last_pos + 1]
self.last = mid
return mid
elif self.new < self.last:
return self.last
class Solution:
def __init__(self):
self.numbers = []
self.last = 0
self.new = 0
def Insert(self, num):
# write code here
if not self.numbers:
self.numbers.append(num)
self.last = num
else:
for i in range(len(self.numbers)):
if self.numbers[i] > num:
self.numbers.insert(i, num)
break
else:
self.numbers.append(num)
self.new = num
def GetMedian(self, x):
# write code here
if len(self.numbers) == 1:
self.last = self.numbers[0]
return self.numbers[0]
elif len(self.numbers) % 2 == 0:
last_pos = self.numbers.index(self.last)
if self.new >= self.last:
return (self.last + self.numbers[last_pos + 1]) / 2.0
elif self.new < self.last:
mid = (self.last + self.numbers[last_pos - 1]) / 2.0
self.last = self.numbers[last_pos - 1]
return mid
elif len(self.numbers) % 2 == 1:
last_pos = self.numbers.index(self.last)
if self.new >= self.last:
mid = self.numbers[last_pos + 1]
self.last = mid
return mid
elif self.new < self.last:
return self.last
发表于 2016-03-06 17:04:33
回复(1)
import java.util.Arrays;
public class Solution {
static int[] seq = new int[0];
public static void Insert(Integer num) {
// int stop = list.size(), start = 0;
int stop = seq.length-1, start = 0;
if(seq.length == 0){
seq = Arrays.copyOf(seq, 1);
seq[0] = num;
}else{
while(stop >= start){
int mid = (start+stop) >>> 1;
if(seq[mid] < num){
start = mid + 1;
}else if(seq[mid] > num){
stop = mid - 1;
}else{ // key == mid
seq = Arrays.copyOf(seq, seq.length+1);
for(int i = seq.length-1;i > mid;i--){
seq[i] = seq[i-1];
}
seq[mid] = num;
break;
}
}
if(start > seq.length-1){//num bigger than last key
seq = Arrays.copyOf(seq, seq.length+1);
seq[start] = num;
}else if(stop < 0){ //num less than first key
seq = Arrays.copyOf(seq, seq.length+1);
for(int i = seq.length-1; i >0;i--){
seq[i] = seq[i-1];
}
seq[start] = num;
}else{ // num in between the seq
seq = Arrays.copyOf(seq, seq.length+1);
for(int i = seq.length-1; i > start;i--){
seq[i] = seq[i-1];
}
seq[start] = num;
}
}
}
public static Double GetMedian() {
int len = seq.length;
if(len %2 ==0){
return (seq[len/2]+seq[len/2-1])/2.0;
}
return seq[len/2]*1.0;
}
}
发表于 2015-08-14 18:20:49
回复(0)
C++ 通过的代码 将数据用堆 分成两部分 小的一部分（大根堆） 大的一部分（小根堆）
class Solution {
private:
vector<int> big_part;
vector<int> small_part;
public:
void Insert(int num)
{
if (small_part.empty()) {
small_part.push_back(num);
}
else {
if (small_part.size() == big_part.size()) {
if (num <= big_part.front()) {
small_part.push_back(num);
push_heap(small_part.begin(), small_part.end());
}
else {
pop_heap(big_part.begin(), big_part.end(), greater<int>());
small_part.push_back(big_part.back());
big_part.back() = num;
push_heap(small_part.begin(), small_part.end());
push_heap(big_part.begin(), big_part.end(), greater<int>());
}
}
else {
if (num >= small_part.front()) {
big_part.push_back(num);
push_heap(big_part.begin(), big_part.end(), greater<int>());
}
else {
pop_heap(small_part.begin(), small_part.end());
big_part.push_back(small_part.back());
small_part.back() = num;
push_heap(small_part.begin(), small_part.end());
push_heap(big_part.begin(), big_part.end(), greater<int>());
}
}
}
}
double GetMedian()
{
if (small_part.size() == big_part.size()) {
return static_cast<double>(small_part.front() + big_part.front()) / 2;
}
else {
return small_part.front();
}
}
};
发表于 2015-05-05 23:20:24
回复(0)
class Solution {
public:
void Insert(int num) {
data.push_back(num);
std::sort(data.begin(), data.end());
}
double GetMedian() {
unsigned int size = data.size();
if (size & 1) {
return data[size >> 1];
} else {
int left = data[(size >> 1) - 1];
int right = data[size >> 1];
return (static_cast<double>(left) + right) / 2;
}
}
private:
vector<int> data;
};
发表于 2016-07-27 21:24:54
回复(1)
class Solution {
priority_queue<int, vector<int>, less<int> > p;
priority_queue<int, vector<int>, greater<int> > q;
public:
void Insert(int num){
if(p.empty() || num <= p.top()) p.push(num);
else q.push(num);
if(p.size() == q.size() + 2) q.push(p.top()), p.pop();
if(p.size() + 1 == q.size()) p.push(q.top()), q.pop();
}
double GetMedian(){
return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();
}
};
/*
//弱弱的数据。。。
class Solution {
vector<int> v;
int n;
public:
void Insert(int num){
v.push_back(num);
n = v.size();
for(int i = n - 1; i > 0 && v[i] < v[i - 1]; --i) swap(v[i], v[i - 1]);
}
double GetMedian(){
return (v[(n - 1) >> 1] + v[n >> 1]) / 2.0;
}
};
*/
编辑于 2015-09-12 12:30:40
回复(79)
python2.7 时间：30ms 内存：5760k class Solution: def __init__(self): self.arr = [] def Insert(self, num): if len(self.arr)==0: self.arr.append(num) else: i = len(self.arr)-1 while num > self.arr[i]: i -= 1 self.arr.insert(i+1,num) def GetMedian(self, no): # write code here length = len(self.arr) if length %2 ==1 : return self.arr[length//2] else: return (self.arr[length//2] + self.arr[length//2-1])/2
发表于 2017-12-11 15:11:28
回复(0)
前后段使用的都是小根堆，只是前半段的小根堆加入的是取负号的元素值，从前半段小根堆pop出最小值（负值），取上负号就是最大值了
from heapq import * # 导入小根堆
class Solution:
pre = [] # 前半部分
after = [] # 后半部分
def Insert(self, num):
pre = self.pre
after = self.after
# 往后半部分添加元素
# 每次从后半部分pop出一个最小值加入前半部分
# 相当于后半部分长度不变，前半部分长度+1
heappush(pre, -heappushpop(after, num))
# 维持前后段元素个数相差不超过1
if len(after) < len(pre):
# 从前半部分pop出一个最小值（这个值是负数，添负号后就是最大值）
# 将添负号后的值（前半部分最大值）加入到后半部分
heappush(after, -heappop(pre))
def GetMedian(self):
pre = self.pre
after = self.after
# 后半部分比前半部分多一位，中位数 = 后半部分[0]
if len(after) > len(pre):
return after[0]
else:
# 中位数 = （后半部分最小值 + 前半部分最大值 ）/ 2
# 因为前部分小根堆里的元素是负值
# pop出最小的负值取负号就能拿到前半部分的最大值
return (after[0] - pre[0]) / 2
发表于 2022-05-18 17:06:05
回复(0)
import java.util.*;
public class Solution {
//堆
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
private PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
public void Insert(Integer num) {
if(maxHeap.isEmpty() || num < maxHeap.peek())
maxHeap.add(num);
else
minHeap.add(num);
modifyTwoHeaps();
}
public Double GetMedian() {
if(maxHeap.size() == minHeap.size())
return ( maxHeap.peek() + minHeap.peek() ) / 2.0;
else
return maxHeap.size() > minHeap.size() ? (double)maxHeap.peek() : (double)minHeap.peek();
}
private void modifyTwoHeaps(){
if(maxHeap.size() == minHeap.size() + 2)
minHeap.add(maxHeap.poll());
if(minHeap.size() == maxHeap.size() + 2)
maxHeap.add(minHeap.poll());
}
}
发表于 2021-09-29 23:28:42
回复(0)
采用插入排序思想即可解决问题。
import java.util.*;
public class Solution {
ArrayList list = new ArrayList();
public void Insert(Integer num) {
int index = list.size();
for(int i=0;i<index;++i){
if(list.get(i)>num){
index = i;
}
}
list.add(index,num);
}
public Double GetMedian() {
int len = list.size();
if(len==0)return null;
int i = len/2;
if(len%2==0)return (double )(list.get(i)+list.get(i-1))/2;
else return (double)list.get(i);
}
}
发表于 2021-09-25 08:43:18
回复(0)
// 从小到大
PriorityQueue<Integer> max = new PriorityQueue<>();
// 从大到小
PriorityQueue<Integer> min = new PriorityQueue<>( (x, y) -> y-x);
public void Insert(Integer num) {
if(max.size() == min.size()){
min.add(num);
max.add(min.poll());
}else{
max.add(num);
min.add(max.poll());
}
}
public Double GetMedian() {
return (Double)( max.size() == min.size() ? (max.peek() + min.peek()) / 2.0 : max.peek());
}
发表于 2021-07-08 14:23:47
回复(0)
问题信息
难度：
757条回答
2453收藏
111976浏览
通过挑战的用户
查看代码-
2023-03-11 17:27:26
-
2023-02-26 23:20:51 -
2023-02-03 22:59:46
-
2023-01-06 17:16:22
-
2022-12-12 18:30:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
