如何得到1個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那末中位數(shù)就是所有數(shù)值排序以后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那末中位數(shù)就是所有數(shù)值排序以后中間兩個(gè)數(shù)的平均值。
劍指offer上說的很詳細(xì)
1.無序數(shù)組
插入：
獲得中位數(shù)：
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.有序數(shù)組
插入：
獲得中位數(shù)：
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.有序鏈表
插入：
獲得中位數(shù)：
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內(nèi)部實(shí)現(xiàn)就是鏈表，這里獲得中位數(shù)是需要1個(gè)1個(gè)的遍歷鏈表的
劍指offer書上定義兩個(gè)指針指向兩邊中間，太復(fù)雜，省略了
4.最大堆，最小堆
插入：
獲得中位數(shù)：
兩個(gè)堆數(shù)據(jù)之差不超過1
抄的程序
優(yōu)先隊(duì)列，可以模型堆嗎？
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());
}
}
}也能夠這樣理解，兩個(gè)數(shù)組，AB，A內(nèi)的元素都比B的小，B內(nèi)的元素都比B的大，A是升序的，B也是升序的
中位數(shù)就是Ａ的最大值和Ｂ的最小值的平均值
插入元素時(shí)候，上面程序是根據(jù)插入數(shù)據(jù)的奇數(shù)偶數(shù)順序選擇插入到對應(yīng)的AB中，這樣很好
奇數(shù)時(shí)候插入到A，A最大值插入到B
偶數(shù)時(shí)候插入到B，B最小值插入到A
可以用兩個(gè)排序數(shù)組
其他樹實(shí)現(xiàn)的太復(fù)雜了，省略了
上一篇 ios多線程 -- GCD介紹
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
