LeetCode 數(shù)據(jù)流中的中位數(shù) [困難]
如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)跃巡？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值什猖。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值票彪，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
例如不狮，
[2,3,4] 的中位數(shù)是 3
[2,3] 的中位數(shù)是 (2 + 3) / 2 = 2.5
設(shè)計(jì)一個(gè)支持以下兩種操作的數(shù)據(jù)結(jié)構(gòu)：
void addNum(int num) - 從數(shù)據(jù)流中添加一個(gè)整數(shù)到數(shù)據(jù)結(jié)構(gòu)中降铸。
double findMedian() - 返回目前所有元素的中位數(shù)。
示例 1：
輸入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
輸出：[null,null,null,1.50000,null,2.00000]
示例 2：
輸入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
輸出：[null,null,2.00000,null,2.50000]
限制：
最多會(huì)對(duì) addNum摇零、findMedia進(jìn)行 50000 次調(diào)用推掸。
題目分析
解法1
使用鏈表實(shí)現(xiàn)，每次進(jìn)行插入的時(shí)候遂黍，都需要進(jìn)行比較终佛，然后插入到何是的位置，那么就是有效位置雾家，同時(shí)記錄插入的此處铃彰，然后取中間的數(shù)據(jù)就是中位數(shù)
解法2
使用數(shù)組實(shí)現(xiàn)，每次進(jìn)行插入的時(shí)候進(jìn)行比較然后移動(dòng)數(shù)組芯咧，那么再取出數(shù)據(jù)的時(shí)候牙捉，就很好實(shí)現(xiàn)竹揍，就是中間值
解法3
使用大根堆(保存較大的一般)和小根堆(保存較小的一半)一起實(shí)現(xiàn)，如果兩個(gè)堆不相等邪铲，則返回大根堆的堆頂芬位，否則返回 AB堆的堆頂?shù)暮偷囊话慵纯?/p>
注意:此題定義為困難可能目的是自己造輪子困難
代碼實(shí)現(xiàn)
public class MedianFinder {
public static void main(String[] args) {
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(15);
medianFinder.addNum(78);
System.out.println(medianFinder.findMedian());
medianFinder.addNum(1);
System.out.println(medianFinder.findMedian());
}
/**
* 因?yàn)樾枰迦霐?shù)據(jù) 如果使用數(shù)組，每次插入之后都要移動(dòng) O(n)次
* 如果使用鏈表 則每次插入都可以直接插入到指定位置上 然后記錄總數(shù)带到，然后取出中位值的時(shí)候昧碉，需要進(jìn)行遍歷
*/
Queue<Integer> A, B;
public MedianFinder() {
A = new PriorityQueue<>();
B = new PriorityQueue<>((x, y) -> (y - x));
}
public void addNum(int num) {
if (A.size() != B.size()) {
A.add(num);
B.add(A.poll());
} else {
B.add(num);
A.add(B.poll());
}
}
public double findMedian() {
return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
}
}
