【排序算法运用】剑指 Offer 41. 数据流中的中位数-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月17日上午11:27

优先队列注意返回值

class MedianFinder {

    /** initialize your data structure here. */
    PriorityQueue<Integer> minQueue, maxQueue;
    public MedianFinder() {
        minQueue = new PriorityQueue<>();//保存大数字，使用小顶堆。
        maxQueue = new PriorityQueue<>((x, y) -> (y - x));//保存小数字，使用大顶堆。
    }
    public void addNum(int num) {
        if(minQueue.size() != maxQueue.size()){
            minQueue.offer(num);
            maxQueue.offer(minQueue.poll());
        }else{
            maxQueue.offer(num);
            minQueue.offer(maxQueue.poll());
        }

    }
    public double findMedian() {
        return minQueue.size() != maxQueue.size() ? minQueue.peek() : (minQueue.peek() + maxQueue.peek()) / 2.0;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月16日下午7:02

from heapq import heapify,heappush,heappop
class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        # 大根堆存放较小的数
        self.bigHeapq = []
        heapify(self.bigHeapq)
        # 小根堆存放较大的数
        self.smallHeapq = []
        heapify(self.smallHeapq)
        self.count = 0

    def addNum(self, num: int) -> None:
        self.count += 1
        # 奇数个
        if self.count & 1 == 1:
            # 先添加到小根堆，将堆顶元素弹出放入大根堆中
            heappush(self.smallHeapq,num)
            s = heappop(self.smallHeapq)
            heappush(self.bigHeapq,-1 * s)
        else:
            # 先添加到大根堆，将堆顶元素弹出放入小根堆中
            heappush(self.bigHeapq, -1 * num)
            s = heappop(self.bigHeapq)
            heappush(self.smallHeapq,-1 * s)

    def findMedian(self) -> float:
        if self.count & 1 == 1:
            return -self.bigHeapq[0]
        else:
            return (self.smallHeapq[0]-self.bigHeapq[0]) / 2.0

0 赞同 0 条回复

lucca 普通 2023年1月16日下午5:52

一个大根堆存 <= 中位数，一个小根堆存 > 中位数

时间复杂度 O(NlogN)
空间复杂度 O(N)

class MedianFinder {
    PriorityQueue<Integer> less, more;
    int cnt = 0;

    public MedianFinder() {
        less = new PriorityQueue<>((a, b) -> b - a); 
        more = new PriorityQueue<>();
    }

    public void addNum(int num) {
        cnt++;
        if (less.isEmpty()) {
            less.add(num);
            return;
        }
        if (num <= less.peek()) {
            less.add(num);
            if (cnt % 2 == 0) more.add(less.poll());
        } else {
            more.add(num);
            if (cnt % 2 == 1) less.add(more.poll());
        }
    }

    public double findMedian() {
        return cnt % 2 == 1 ?
                less.peek() :
                (1.0 * less.peek() + more.peek()) / 2;
    }
}

0 赞同 0 条回复

庄重普通 2023年1月12日上午10:34

// 思路：
//     1.使用两个优先队列
//     2.如果两个队列大小相等，两个队列的队头为最中间的两个数，中位数为二者之和除2
//     3.如果两个队列大小不相等，插入时会保存在较大的队列中,因此中位数为较大的队顶
class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int, vector<int>, less<int>> queMin;//排序由大到小，保存较小的
    priority_queue<int, vector<int>, greater<int>> queMax;//排序由小到大,保存较大的

    MedianFinder() {}

    void addNum(int num) {
        if(queMax.size() == queMin.size()){
            queMin.push(num);
            queMax.push(queMin.top());
            queMin.pop();
        }
        else{
            queMax.push(num);
            queMin.push(queMax.top());
            queMax.pop();
        }
    }

    double findMedian() {
        if(queMax.size() == queMin.size()){
            return (queMin.top() + queMax.top()) / 2.0;
        }
        else{
            return queMax.top() * 1.0;
        }
    }
};
// 时间复杂度:查找中位数 O(1)， 插入元素：O(logn)
// 空间复杂度：O(n)

0 赞同 0 条回复

波波_1936 普通 2022年12月4日下午8:28

/**
     * 剑指 Offer 41. 数据流中的中位数
     *
     */
    class MedianFinder {


        //思路： 使用大顶堆和小顶堆来实现
        //保持 minQueue.size()-maxQueue.size<=1
        PriorityQueue<Integer> minQueue;
        PriorityQueue<Integer> maxQueue;

        /** initialize your data structure here. */
        public MedianFinder() {
            minQueue = new PriorityQueue<>();
            maxQueue = new PriorityQueue<>((o1, o2) -> o2-o1);

        }

        public void addNum(int num) {
            maxQueue.add(num);
            minQueue.add(maxQueue.poll());
            if(maxQueue.size()+1<minQueue.size()){
                maxQueue.add(minQueue.poll());
            }
        }

        public double findMedian() {
            if (minQueue.size()>maxQueue.size()) return minQueue.peek();
            return (double) (minQueue.peek()+maxQueue.peek())/2;
        }
    }

0 赞同 0 条回复

@ 普通 2022年12月3日上午10:34

思路：优先队列

class MedianFinder {
    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;
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:43

type maxHeap []int  // 大顶堆
type minHeap []int  // 小顶堆

// 每个堆都要heap.Interface的五个方法：Len, Less, Swap, Push, Pop
// 其实只有Less的区别。

// Len 返回堆的大小
func (m maxHeap) Len() int {
    return len(m)
}
func (m minHeap) Len() int {
    return len(m)
}

// Less 决定是大优先还是小优先
func (m maxHeap) Less(i, j int) bool {  // 大根堆
    return m[i] > m[j]
}
func (m minHeap) Less(i, j int) bool {  // 小根堆
    return m[i] < m[j]
}

 // Swap 交换下标i, j元素的顺序
func (m maxHeap) Swap(i, j int) {  
    m[i], m[j] = m[j], m[i]
}
func (m minHeap) Swap(i, j int) {   
    m[i], m[j] = m[j], m[i]
}

// Push 在堆的末尾添加一个元素，注意和heap.Push(heap.Interface, interface{})区分
func (m *maxHeap) Push(v interface{}) {
    *m = append(*m, v.(int))
}
func (m *minHeap) Push(v interface{}) {
    *m = append(*m, v.(int))
}

// Pop 删除堆尾的元素，注意和heap.Pop()区分
func (m *maxHeap) Pop() interface{} {
    old := *m
    n := len(old)
    v := old[n - 1]
    *m = old[:n - 1]
    return v
}
func (m *minHeap) Pop() interface{} {
    old := *m
    n := len(old)
    v := old[n - 1]
    *m = old[:n - 1]
    return v
}

// MedianFinder 维护两个堆，前一半是大顶堆，后一半是小顶堆，中位数由两个堆顶决定
type MedianFinder struct {  
    maxH *maxHeap
    minH *minHeap
}

// Constructor 建两个空堆
func Constructor() MedianFinder {
    return MedianFinder{
        new(maxHeap),
        new(minHeap),
    }
}

// AddNum 插入元素num
// 分两种情况插入：
// 1. 两个堆的大小相等，则小顶堆增加一个元素（增加的不一定是num）
// 2. 小顶堆比大顶堆多一个元素，大顶堆增加一个元素
// 这两种情况又分别对应两种情况：
// 1. num小于大顶堆的堆顶，则num插入大顶堆
// 2. num大于小顶堆的堆顶，则num插入小顶堆
// 插入完成后记得调整堆的大小使得两个堆的容量相等，或小顶堆大1
func (m *MedianFinder) AddNum(num int)  {
    if m.maxH.Len() == m.minH.Len() {
        if m.minH.Len() == 0 || num >= (*m.minH)[0] {
            heap.Push(m.minH, num)
        } else {
            heap.Push(m.maxH, num)
            top := heap.Pop(m.maxH).(int)
            heap.Push(m.minH, top)
        }
    } else {
        if num > (*m.minH)[0] {
            heap.Push(m.minH, num)
            bottle := heap.Pop(m.minH).(int)
            heap.Push(m.maxH, bottle)
        } else {
            heap.Push(m.maxH, num)
        }
    }
}

// FindMediam 输出中位数
func (m *MedianFinder) FindMedian() float64 {
    if m.minH.Len() == m.maxH.Len() {
        return float64((*m.maxH)[0]) / 2.0 + float64((*m.minH)[0]) / 2.0
    } else {
        return float64((*m.minH)[0])
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年12月1日下午3:05

/**
套路题：使用两个优先队列
 */
class MedianFinder {
    Queue<Integer> large;
    Queue<Integer> small;
    /** initialize your data structure here. */
    public MedianFinder() {
        large = new PriorityQueue<>();//large使用小根堆，保证堆顶最小
        small = new PriorityQueue<>((a,b)->b-a);//small使用小根堆，保证堆顶最大
    }
    //O(logN)
    public void addNum(int num) {
        //放入large中，维护大小差距小于等于1
        if(small.size() >= large.size()) {
            small.offer(num);
            //大数中加入的一定是小数中最大的，维护大根堆最小的大于等于小根堆最大的
            large.offer(small.poll());
        }else {
            large.offer(num);
            small.offer(large.poll());
        }
    }
    //O(1)
    public double findMedian() {
        if (large.size() > small.size()) {
            return large.peek();
        }else if(large.size() < small.size()) {
            return small.peek();
        }
        return (large.peek()+small.peek()) / 2.0;
    }
}

0 赞同 0 条回复

T 普通 2022年11月29日下午4:14

下面代码

class MedianFinder {
    Queue<Integer> A, B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();//小顶堆
        B = new PriorityQueue<>(Comparator.reverseOrder());//大顶堆
    }

    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;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年11月25日下午4:14

时间复杂度O(logn)

class MedianFinder {
    //大顶堆、小顶堆实现
    //大根堆：较小元素、小根堆：较大元素
    Queue<Integer> min, max;

    /** initialize your data structure here. */
    public MedianFinder() {
        min = new PriorityQueue<>();
        max = new PriorityQueue<>((x,y)->(y-x));

    }

    //添加元素
    public void addNum(int num) {
        //判断是否为偶数或奇数的情况
        if (min.size() == max.size()){
            min.add(num);
            max.add(min.poll());
        }else{
            max.add(num);
            min.add(max.poll());
        }

    }

    public double findMedian() {
        if (min.size() == max.size()){
            return (min.peek() + max.peek())/2.0;
        }else{
            return max.peek() * 1.0;
        }

    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

0 赞同 0 条回复

lobort 普通 2022年11月21日下午8:18

class MedianFinder {
    Queue<Integer> min,max;
    /** initialize your data structure here. */
    public MedianFinder() {
        max = new PriorityQueue<>();  //小根堆 保存较大的一部分
        min = new PriorityQueue<>((x, y) -> (y - x));  //大根堆 保存较小的一部分
    }

    public void addNum(int num) {
        if(min.size() == max.size()){
            min.add(num);
            max.add(min.poll());
        }else{
            max.add(num);
            min.add(max.poll());
        }
    }

    public double findMedian() {
        if(min.size() == max.size()){
            return ((min.peek() + max.peek()) /2.0 );
        }else{
            return max.peek() * 1.0;
        }
    }
}

0 赞同 0 条回复

派大星普通 2022年11月19日下午10:14

public class Solution12 {
//使用List集合来收集数据
//空间复杂度O(1)
    List<Integer> list;

    public void MedianFinder() {
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        list.add(num);
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
    }

    public double findMedian() {
         if(list.size() == 0)return 0;
         if(list.size() == 1)return list.get(0);
         if(list.size() % 2 == 0){
             double a = (double)list.get(list.size()/2);
             double b = (double)list.get(list.size()/2 - 1);
             return (a + b)/2;
         }else {
             return (double) list.get((list.size()-1)/2);
         }
    }

}

0 赞同 0 条回复

mpweixin用户普通 2022年11月19日下午1:42

分别用大顶堆和小顶堆去存一半的数字

“`c++
class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue> qmax; //大顶堆
priority_queue, greater> qmin; //小顶堆
MedianFinder() {

}

void addNum(int num) {
    if(qmax.empty() || num <= qmax.top()) qmax.push(num);
    else qmin.push(num);
}

double findMedian() {
    while(qmin.size() > qmax.size()) {
        qmax.push(qmin.top());
        qmin.pop();
    }
    while(qmax.size() > qmin.size()+1){
        qmin.push(qmax.top());
        qmax.pop();
    }
    //偶数
    if(qmax.size() > qmin.size()) return qmax.top();
    //奇数
    return (qmax.top() + qmin.top()) / 2.0;
}

};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/

“`

0 赞同 0 条回复

So 普通 2022年11月19日下午1:20

class MedianFinder {
    Queue<Integer> min, max;
    /** initialize your data structure here. */
    public MedianFinder() {
        min = new PriorityQueue<>();
        max = new PriorityQueue<>((x, y) -> (y - x));
    }

    public void addNum(int num) {
        if (min.size() == max.size()) {
            min.add(num);
            max.add(min.poll());
        } else {
            max.add(num);
            min.add(max.poll());
        }
    }

    public double findMedian() {
        if (min.size() == max.size()) {
            return (min.peek() + max.peek()) / 2.0;
        } else {
            return max.peek() * 1.0;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

时间：O(logn)，空间：O(n)

0 赞同 0 条回复

just 普通 2022年11月19日上午11:50

//利用两个堆，将数组一分为二，前一半的数存到大根堆中，后一半的数存到小根堆中，这样的话就可以从两个堆的堆顶求取中位数
class cmpB{
public:
bool operator()(int& a,int& b){
return a>b;
}
};
class cmpA{
public:
bool operator()(int& a ,int& b){
return a<b;
}

};
class MedianFinder {
private:
priority_queue<int,vector,cmpA> queA;
priority_queue<int,vector,cmpB> queB;
int numa;
int numb;

public:
/** initialize your data structure here. */
MedianFinder() {
numa=0;
numb=0;

}

void addNum(int num) {
    if(numa==numb){
        queA.push(num);
        num=queA.top();
        queA.pop();
        queB.push(num);
        numb++;
    }
    else{
        queB.push(num);
        num=queB.top();
        queB.pop();
        queA.push(num);
        numa++;
    }

}

double findMedian() {
    int a=queA.top();
    int b=queB.top();
    return numa==numb? (double)(a+b)/2:b;

}

};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月18日下午9:58

时间复杂度：查找中位数 O(1)插入元素：O(logn) 空间复杂度：O(n)

class MedianFinder {
    Queue<Integer> min;
    Queue<Integer> max;
    /** initialize your data structure here. */
    public MedianFinder() {
        max = new PriorityQueue<>((v1,v2) -> v2 - v1);
        min = new PriorityQueue<>((v1,v2) -> v1 - v2);
    }

    public void addNum(int num) {
        if((max.size() + min.size()) % 2 == 1){
            max.offer(num);
            min.offer(max.poll());
        }else{
            min.offer(num);
            max.offer(min.poll());
        }
    }

    public double findMedian() {
        if((max.size() + min.size()) % 2 == 1){
            return max.peek() * 1.0;
        }else{
            return (min.peek()+max.peek())/2.0;
        }
    }
}

0 赞同 0 条回复

青木普通 2022年11月18日下午9:02

/**
    用两个堆来保存大的部分，和小的部分
    小顶堆保存大的部分，大顶堆保存小的部分，正好每个堆的根就是中间位置
    小顶堆的容量大于等与大顶堆
    如果两个堆容量相同，则说明是偶数，直接相加除2
    反之，将小顶堆的根值输出

    时间:
        查询O(1)
        添加O(logn)
    空间O(n)
 */

class MedianFinder {
    Queue<Integer> qMin,qMax;

    /** initialize your data structure here. */
    public MedianFinder() {
        qMin = new PriorityQueue<>((x,y)->(x-y));
        qMax = new PriorityQueue<>((x,y)->(y-x));
    }

    public void addNum(int num) {
        if(qMin.size() != qMax.size()){
            qMin.offer(num);
            qMax.offer(qMin.poll());
        }
        else{
            qMax.offer(num);
            qMin.offer(qMax.poll());
        }
    }

    public double findMedian() {
        return qMin.size()==qMax.size() ? (qMax.peek()+qMin.peek())/2.0 : qMin.peek();
    }
}

0 赞同 0 条回复

【排序算法运用】剑指 Offer 41. 数据流中的中位数

共以下 17 个回答

一个大根堆存 <= 中位数，一个小根堆存 > 中位数

# 回答此问题取消回复

【排序算法运用】剑指 Offer 41. 数据流中的中位数

共以下 17 个回答

一个大根堆存 <= 中位数，一个小根堆存 > 中位数

# 回答此问题 取消回复

# 回答此问题取消回复