如何得到1個數據流中的中位數？如果從數據流中讀出奇數個數值，那末中位數就是所有數值排序以后位于中間的數值。如果從數據流中讀出偶數個數值，那末中位數就是所有數值排序以后中間兩個數的平均值。
劍指offer上說的很詳細
1.無序數組
插入：
獲得中位數：
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.有序數組
插入：
獲得中位數：
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.有序鏈表
插入：
獲得中位數：
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.最大堆，最小堆
插入：
獲得中位數：
兩個堆數據之差不超過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介紹
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
