剑指offer_数据流中的中位数

淩亂°似流年 2022-06-09 00:19 156阅读 0赞

/*
    如何得到一个数据流中的中位数？
    如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
    如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
    
    思路1：
    采用ArrayList存储元素，每次添加一个元素就进行排序，排序调用Collections的sort函数，时间复杂度O(nlgn)
    排序后的ArrayList可以在O(1)得到中位数
    
    剑指offer思路：
    1.不对数组进行排序，在O(1)时间插入元素，
      采用partition在O(n)时间寻找中位数
    2.每插入一个元素就进行排序，时间O(n)，
      在O(1)时间得到中位数
    3.用链表存储元素，按顺序插入元素到链表，时间O(n)，
      用指针记录中间结点的位置，可以在O(1)时间得到中位数
    4.用二叉搜索树，插入数据可以在平均O(lgn)时间完成，树极度不平衡时最差，O(n)
      在二叉树中添加一个表示子树结点数目的字段，可以在平均O(lgn)时间找到中位数，怎么找？
    5.利用平衡二叉树AVL，插入数据可以在O(lgn)时间完成，把AVL树的平衡因子改为左右子树结点数目差，可以在O(1)时间得到中位数
    
    6.如果能保证数据容器左边的数据都小于右边的数据，这样即使两边内部的数据没有排序，也可以根据左边最大数和右边最小数得到中位数
      左边使用最大堆，右边使用最小堆
      为保证数据平均分配到两个堆中，数据总数目是偶数时新数据插入到最小堆中，否则插入到最大堆中
      为保证左边的数据总数小于右边的数据，数据总数目是偶数时，先将新数据插入最大堆中，再将最大堆的最大元素取出插入最小堆
    									  否则，先将新数据插入最小堆中，再将最小堆的最小元素取出插入最大堆
    用什么来实现最大最小堆？要做到动态插入，参考算法导论优先队列
    
    牛客网参考代码中采用最大最小堆的都直接调用优先队列PriorityQueue，自己如何实现？
    */
    
    import java.util.*;
    
    class  GetMedian
    {
    	//思路1
    	ArrayList<Integer> al=new ArrayList<Integer>();
    	public  void insert(Integer num) {
    		al.add(num);
    		Collections.sort(al);
        }
    
        public  Double getMedian() {
            
    		int s=al.size();
    		double mid=0.0;
    		if (s%2==0)
    		{
    			mid=(double)(al.get(s/2-1)+al.get(s/2))/2;
    		}else
    			mid=al.get(s/2);
    
    		return mid;
        }
    
    	//使用PriorityQueue
    	
    	PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>();
    
    	//PriorityQueue默认是小顶堆，实现大顶堆，需要反转默认排序器
    	PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(20, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
    
    	int count=0;
    	public  void insert1(Integer num) {
    		count++;
    
    		if (count%2==0)
    		{
    			maxHeap.add(num);
    			int max=maxHeap.poll();
    			minHeap.add(max);
    		}else
    		{
    			minHeap.add(num);
    			int min=minHeap.poll();
    			maxHeap.add(min);
    		}	
        }
    
        public  Double getMedian1() {
            
    		if (count%2==0)
    		{
    			int min=minHeap.peek();
    			int max=maxHeap.peek();
    			return (double)(min+max)/2;
    		}else
    		
    			return maxHeap.peek();	
        }
    }