程序员人生网站导航

数据流中的中位数

栏目：php教程时间：2016-07-13 08:51:20

题目

如何得到1个数据流中的中位数？如果从数据流中读出奇数个数值，那末中位数就是所有数值排序以后位于中间的数值。如果从数据流中读出偶数个数值，那末中位数就是所有数值排序以后中间两个数的平均值。

解题

剑指offer上说的很详细
1.无序数组
插入：O(1)
获得中位数：O(N)

import java.util.*;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public void Insert(Integer num) {
        list.add(num);
    }

    public Double GetMedian() {
        int size = list.size();
        Collections.sort(list);
        if(size%2==1){
            return 1.0*list.get(size/2);
        }else{
            return (list.get(size/2) + list.get(size/2-1))/2.0;
        }
    }

}

2.有序数组
插入：O(N)
获得中位数：O(1)

import java.util.*;
public class Solution {
    ArrayList<Integer> list = new ArrayList<Integer>();
    public void Insert(Integer num) {
        int i =0;
        while(i<list.size()){
            if(list.get(i)<=num){
                i++;
            }else
                break;
        }
        list.add(-1);
        int j = list.size() -1;
        while(j>i){
            list.set(j,list.get(j-1));
            j--;
        }
        list.set(i,num);
    }

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

}

3.有序链表
插入：O(N)
获得中位数：O(N)

import java.util.*;

public class Solution {
    LinkedList<Integer> list = new  LinkedList<Integer>();

    public void Insert(Integer num) {
        if(list.size() < 1){
            list.add(num);
            return;
        }
        int i = 0;
        while(i<list.size()){
            if(list.get(i) <=num)
                i++;
            else
                break;
        }
        list.add(i,num);

    }

    public Double GetMedian() {
        if( list.size() < 1 ) return null;
        if((list.size()&1) == 1){
            return list.get(list.size()/2)+0.0;
        }else{
            return (list.get((list.size()-1)/2)+list.get(list.size()/2)+0.0)/2;
        }
    }

}

LinkedList内部实现就是链表，这里获得中位数是需要1个1个的遍历链表的
剑指offer书上定义两个指针指向两边中间，太复杂，省略了

4.最大堆，最小堆
插入：O(log(n))
获得中位数：O(1)
两个堆数据之差不超过1
抄的程序
优先队列，可以模型堆吗？

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

public class Solution {
    int count = 0;
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>(11, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public void Insert(Integer num) {
         count++;
        if (count % 2 == 0) {
            maxHeap.offer(num);
            int i = maxHeap.poll();
            minHeap.offer(i);
        } else {
            minHeap.offer(num);
            int i = minHeap.poll();
            maxHeap.offer(i);
        }

    }

    public Double GetMedian() {
        if (count % 2 == 0) {
            return (Double.valueOf(maxHeap.peek()) +Double.valueOf( minHeap.peek())) / 2;
        } else {
            return Double.valueOf(maxHeap.peek());
        }
    }

}

也能够这样理解，两个数组，AB，A内的元素都比B的小，B内的元素都比B的大，A是升序的，B也是升序的
中位数就是Ａ的最大值和Ｂ的最小值的平均值
插入元素时候，上面程序是根据插入数据的奇数偶数顺序选择插入到对应的AB中，这样很好
奇数时候插入到A，A最大值插入到B
偶数时候插入到B，B最小值插入到A
可以用两个排序数组

其他树实现的太复杂了，省略了

------分隔线----------------------------

上一篇 ios多线程 -- GCD介绍

下一篇 工作流框架Activiti常用功能初探

------分隔线----------------------------