題目描述

????假設(shè)我們有一個實時輸入的整數(shù)管道流狐胎，現(xiàn)在要求輸出這些數(shù)據(jù)流的中位數(shù)特姐。

思路分析

????常規(guī)思路同木，我們可將所有數(shù)據(jù)排序浮梢，然后以O(shè)(1)時間復雜度取其中位數(shù)。但排序的耗費太大彤路，所以我們得另尋他法秕硝。用一個最大堆實現(xiàn)中位數(shù)左邊位置的存儲，最小堆實現(xiàn)右邊位置的存儲洲尊，往堆中插入一個數(shù)據(jù)的時間復雜度是O(log(n))远豺，取得中位數(shù)的時間復雜度是O(1)，并且Java中的PriorityQueue已經(jīng)幫我們實現(xiàn)了堆的相關(guān)操作坞嘀。

Java代碼實現(xiàn)

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

/**
 * 獲取實時數(shù)據(jù)流的中位數(shù)躯护，本代碼借用最大堆和最小堆思想實現(xiàn)
 * @author Administrator
 * @version 2018/10/24
 */
public class Exe43_GetMidData {
    
    public static void main(String[] args) {
        
        int[] testDatas={10,20,1,19,28,34,54,33,9,13,12,17,15};
        System.out.println(solution(testDatas));
        
    }
    
    public static double solution(int[] datas) {
        
        if(datas==null||datas.length==0){
            throw new IllegalArgumentException();
        }else {
            
            double midData=-1;
            //小頂堆
            Queue<Integer> minHeap=new PriorityQueue<Integer>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1-o2;
                }
            });
            //大頂堆
            Queue<Integer> maxHeap=new PriorityQueue<Integer>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
            for(int i=1;i<=datas.length-1;i++){
                if((i&1)==1){//奇數(shù)，插入大頂堆
                    maxHeap.add(datas[i]);
                }else {//偶數(shù)丽涩，插入小頂堆
                    maxHeap.add(datas[i]);
                    minHeap.add(maxHeap.poll());
                }
            }
            if((datas.length&1)==1){
                midData=minHeap.peek();
            }else {
                midData=(minHeap.peek()+maxHeap.peek())/2.0;
            }
            return midData;
            
        }
        
    }

}