首页 > 试题广场 >

数据流中的中位数

[编程题]数据流中的中位数
  • 热度指数:418292 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

数据范围:数据流中数个数满足 ,大小满足

进阶: 空间复杂度 , 时间复杂度
示例1

输入

[5,2,3,4,1,6,7,0,8]

输出

"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "

说明

数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...   
示例2

输入

[1,1,1]

输出

"1.00 1.00 1.00 "
import java.util.ArrayList;
import java.util.Collections;
public class Solution {

    static ArrayList<Integer> list = new ArrayList<>();
    public static void Insert(Integer num) {
        list.add(num);
        Collections.sort(list);
    }

    public static Double GetMedian() {
        if (list.size() % 2 == 0) {
            int l = list.get(list.size()/2);
            int r = list.get(list.size()/2 - 1);
            return (l + r)/2.0;
        }
        else {
            return list.get(list.size()/2)/1.0;
        }
    }


}

发表于 2018-06-27 17:59:30 回复(0)
更多回答
前言:
Java的PriorityQueue 是从JDK1.5开始提供的新的数据结构接口,默认内部是自然排序,结果为小顶堆,也可以自定义排序器,比如下面反转比较,完成大顶堆。

思路:
为了保证插入新数据和取中位数的时间效率都高效,这里使用大顶堆+小顶堆的容器,并且满足:
1、两个堆中的数据数目差不能超过1,这样可以使中位数只会出现在两个堆的交接处;
2、大顶堆的所有数据都小于小顶堆,这样就满足了排序要求。

最后再贴张不同数据结构对应的时间复杂度:

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    int count;
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
	PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
		@Override
		public int compare(Integer o1, Integer o2) {
            //PriorityQueue默认是小顶堆,实现大顶堆,需要反转默认排序器
			return o2.compareTo(o1); 
		}
	});

    public void Insert(Integer num) {
    count++;
    if (count & 1) == 0) { // 判断偶数的高效写法
			if (!maxHeap.isEmpty() && num < maxHeap.peek()) {
				maxHeap.offer(num);
				num = maxHeap.poll();
			}
			minHeap.offer(num);
		} else {
			if (!minHeap.isEmpty() && num > minHeap.peek()) {
				minHeap.offer(num);
				num = minHeap.poll();
			}
			maxHeap.offer(num);
		}
    }

    public Double GetMedian() {    
        if(count==0)
            throw new RuntimeException("no available number!");
        double result;
       //总数为奇数时,大顶堆堆顶就是中位数
       if((count&1)==1)
            result=maxHeap.peek();
        else
            result=(minHeap.peek()+maxHeap.peek())/2.0;
        return result;
    }
}

编辑于 2016-07-15 17:49:30 回复(27)
#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)
//大家好,我来了!欢迎点赞!
class Solution {
private:
		vector<int> min;
		vector<int> max;
public:
    	void Insert(int num)
    	{
    	   if(((min.size()+max.size())&1)==0)//偶数时 ,放入最小堆 
		   {
		   	  if(max.size()>0 && num<max[0])
		   	  {
		   	  	// push_heap (_First, _Last),要先在容器中加入数据,再调用push_heap ()
		   	  	 max.push_back(num);//先将元素压入容器
		   	  	 push_heap(max.begin(),max.end(),less<int>());//调整最大堆 
				 num=max[0];//取出最大堆的最大值 
				 //pop_heap(_First, _Last),要先调用pop_heap()再在容器中删除数据
				 pop_heap(max.begin(),max.end(),less<int>());//删除最大堆的最大值 
				 max.pop_back(); //在容器中删除 
			  }
			  min.push_back(num);//压入最小堆 
			  push_heap(min.begin(),min.end(),greater<int>());//调整最小堆 
		   }
		   else//奇数时候,放入最大堆
		   {
		   	  if(min.size()>0 && num>min[0])
		   	  {
		   	  	// push_heap (_First, _Last),要先在容器中加入数据,再调用push_heap ()
			     min.push_back(num);//先压入最小堆 
				 push_heap(min.begin(),min.end(),greater<int>());//调整最小堆 
				 num=min[0];//得到最小堆的最小值(堆顶) 
				 //pop_heap(_First, _Last),要先调用pop_heap()再在容器中删除数据
				 pop_heap(min.begin(),min.end(),greater<int>());//删除最小堆的最大值 
				 min.pop_back(); //在容器中删除 
			  }
		   	  max.push_back(num);//压入数字 
		   	  push_heap(max.begin(),max.end(),less<int>());//调整最大堆 
		   }	
		}
		/*获取中位数*/		
		double GetMedian()
		{
			int si敏感词.size()+max.size();
			if(size<=0) //没有元素,抛出异常 
			    return 0;//throw exception("No numbers are available");
			if((size&1)==0)//偶数时,去平均 
			    return ((double)(max[0]+min[0])/2);
			else//奇数,去最小堆,因为最小堆数据保持和最大堆一样多,或者比最大堆多1个 
			    return min[0];
		}
};

编辑于 2016-07-28 19:20:05 回复(9)

python solution

题目有问题,自己要加一个参数,默认少了一个参数!!!

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr = []

    def Insert(self, num):
        self.arr.append(num)
        self.arr.sort()

    def GetMedian(self, ***):
        length = len(self.arr)
        if length % 2 == 1:
            return self.arr[length // 2]
        return (self.arr[length // 2] + self.arr[length // 2 - 1]) / 2.0
编辑于 2019-08-09 20:35:02 回复(16)

PYTHON

参考:https://leetcode.com/problems/find-median-from-data-stream/discuss/74062/Short-simple-JavaC++Python-O(log-n)-+-O(1)
使用两个堆:

  • 大根堆:large保存大的半数的数据
  • 小根堆:small保存小的半数的数据
    获取中位数的时间复杂度为O(1),插入一个数据的时间复杂度为O(log(n))

技巧:

  1. 构造小根堆时,对数组元素取负值来构造
  2. heappush(heap,data),将deat放入大根堆中
  3. heapposh(heap),弹出heap中的最小值
  4. 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)
import java.util.*;
// 运行时间:23ms
// 占用内存:9104k
public class Solution {
    ArrayList<Integer> res = new ArrayList<>();
    public void Insert(Integer num) {
        res.add(num);
        Collections.sort(res);
    }

    public Double GetMedian() {
        int n = res.size();
        if (n % 2 == 0) {
            return Double.valueOf((res.get(n / 2) + res.get(n / 2 - 1)) / 2.0);
        } else {
            return Double.valueOf(res.get(n / 2));
        }
    }
}
发表于 2017-12-25 17:01:02 回复(8)

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 {
	ArrayList<Integer> al = new ArrayList<Integer>();
    public void Insert(Integer num) {
    	al.add(num);
        Collections.sort(al);
    }

    public Double GetMedian() {
        int mid = al.size()/2;
        if((al.size()&1) == 0){
            Integer n1 = al.get(mid);
            Integer n2 = al.get(mid - 1);
            double s = (Double.valueOf(n1 + "") + Double.valueOf(n2 + ""))/2;
            return s;
        }else{
            double s = Double.valueOf(al.get(mid) + "");
            return s;
        }
    }


}

发表于 2015-10-18 00:27:59 回复(5)
用两个堆,一个大顶堆,一个小顶堆。

先往小顶堆里面存数,并保持: 0 <= 小顶堆的size()-大顶堆的size() <= 1

保持两边数量几乎一致就需要在插入的时候进行比较、调整。

返回中位数的时候,如果小顶堆和大顶堆size()相同,就返回他们堆顶元素的平均值;否则返回小顶堆的堆顶元素。

这种方法插入时间复杂度是O(log n),返回中位数的时间复杂度是O(1)
发表于 2015-04-17 09:52:06 回复(0)
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
发表于 2016-03-06 17:04:33 回复(1)
Ron头像 Ron
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)