295. 数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

1、python:

import heapq
import json

class MedianFinder:

    def __init__(self):
        self.queMin = list()
        self.queMax = list()

    def addNum(self, num: int) -> None:
        queMin_ = self.queMin
        queMax_ = self.queMax

        if not queMin_ or num <= -queMin_[0]:
            heapq.heappush(queMin_, -num)
            if len(queMax_) + 1 < len(queMin_):
                heapq.heappush(queMax_, -heapq.heappop(queMin_))
        else:
            heapq.heappush(queMax_, num)
            if len(queMax_) > len(queMin_):
                heapq.heappush(queMin_, -heapq.heappop(queMax_))

    def findMedian(self) -> float:
        queMin_ = self.queMin
        queMax_ = self.queMax

        if len(queMin_) > len(queMax_):
            return -queMin_[0]
        return (-queMin_[0] + queMax_[0]) / 2

if __name__ == '__main__':
    command = json.loads(input().strip())
    num_pool = json.loads(input().strip())

    finder = MedianFinder()

    for i, m in enumerate(command):
        if m == "MedianFinder":
            pass
        elif m == "addNum":
            finder.addNum(num_pool[i][0])
        elif m == "findMedian":
            print(finder.findMedian())

2、java: 

疑问：java有像python range()那样限制吗？有像python的enumerate()方法吗？

import com.alibaba.fastjson.JSON;

import java.nio.charset.StandardCharsets;
import java.util.PriorityQueue;
import java.util.Scanner;

class MedianFinder {
    PriorityQueue<Integer> queMin;
    PriorityQueue<Integer> queMax;

    public MedianFinder() {
        queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
        queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
    }

    public void addNum(int num) {
        if (queMin.isEmpty() || num <= queMin.peek()) {
            queMin.offer(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.offer(queMin.poll());
            }
        } else {
            queMax.offer(num);
            if (queMax.size() > queMin.size()) {
                queMin.offer(queMax.poll());
            }
        }
    }

    public double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.peek();
        }
        return (queMin.peek() + queMax.peek()) / 2.0;
    }
}

class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
        String[] command = JSON.parseObject(cin.nextLine(), String[].class);
        int[][] numPool = JSON.parseObject(cin.nextLine(), int[][].class);

        MedianFinder finder = new MedianFinder();

        for (int i=0; i < command.length; i++) {
            if (command[i].equals("MedianFinder")) {
                // System.out.println();
            } else if (command[i].equals("addNum")) {
                finder.addNum(numPool[i][0]);
            } else if (command[i].equals("findMedian")) {
                System.out.println(finder.findMedian());
            }

        }
    }
}

3、go:

package main

import (
    "container/heap"
    "encoding/json"
    "fmt"
    "sort"
)

type MedianFinder struct {
    queMin, queMax hp
}

func Constructor() MedianFinder {
    return MedianFinder{}
}

func (mf *MedianFinder) AddNum(num int) {
    minQ, maxQ := &mf.queMin, &mf.queMax
    if minQ.Len() == 0 || num <= -minQ.IntSlice[0] {
        heap.Push(minQ, -num)
        if maxQ.Len()+1 < minQ.Len() {
            heap.Push(maxQ, -heap.Pop(minQ).(int))
        }
    } else {
        heap.Push(maxQ, num)
        if maxQ.Len() > minQ.Len() {
            heap.Push(minQ, -heap.Pop(maxQ).(int))
        }
    }
}

func (mf *MedianFinder) FindMedian() float64 {
    minQ, maxQ := mf.queMin, mf.queMax
    if minQ.Len() > maxQ.Len() {
        return float64(-minQ.IntSlice[0])
    }
    return float64(maxQ.IntSlice[0]-minQ.IntSlice[0]) / 2
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }


func main() {
    var commandInput string
    var numInput string
    if _, err := fmt.Scanf("%s\n%s", &commandInput, &numInput); err != nil {
        println("err:", err)
        return
    }

    command := make([]string, 0)
    if commandJsonErr := json.Unmarshal([]byte(commandInput), &command); commandJsonErr != nil {
        println(commandJsonErr)
        return
    }
    num := make([][]int, 0)
    if numJsonErr := json.Unmarshal([]byte(numInput),&num); numJsonErr != nil {
        println(numJsonErr)
        return
    }

    finder := Constructor()
    for i := 0; i < len(command); i++ {
        if command[i] == "MedianFinder" {
            //println()
        } else if command[i] == "addNum" {
            finder.AddNum(num[i][0])
        } else if command[i] == "findMedian" {
            println(int32(finder.FindMedian()))
        }
    }

}

 4、C++:

#include <vector>
#include <queue>
#include <iostream>
#include ".\lib\json-3.9.1\single_include\nlohmann\json.hpp"
using json = nlohmann::json;
using namespace std;


class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;

    MedianFinder() {}

    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) {
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.push(queMin.top());
                queMin.pop();
            }
        } else {
            queMax.push(num);
            if (queMax.size() > queMin.size()) {
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }

    double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.top();
        }
        return (queMin.top() + queMax.top()) / 2.0;
    }
};

int main() {
    string commandInput;
    getline(cin, commandInput);
    string numInput;
    getline(cin, numInput);

    auto commandJson = json::parse(commandInput, nullptr, false);
    vector<string> command = commandJson;
    auto numJson = json::parse(numInput, nullptr, false);
    vector<vector<int>> num = numJson;

    auto finder = MedianFinder();

    for (int i=0;  i<command.size(); i++) {
        if (command[i] == "MedianFinder") {
            //
        } else if (command[i] == "addNum") {
            finder.addNum(num[i][0]);
        } else if (command[i] == "findMedian") {
            cout << finder.findMedian() << endl;
        }
    }
}