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

扣子普通 2024年4月4日下午9:40

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

}

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

0 赞同 0 条回复

神经蛙普通 2024年3月30日上午11:48

class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {

}

void addNum(int num) {
    // 如果是偶数
    if(min_heap.size() == max_heap.size()){
        max_heap.push(num);
        min_heap.push(max_heap.top());
        max_heap.pop();
    } else {
        min_heap.push(num);
        max_heap.push(min_heap.top());
        min_heap.pop();
    }
}

double findMedian() {
    // 如果是偶数
    if(min_heap.size() == max_heap.size()){
        return (min_heap.top() + max_heap.top()) / 2.0;
    } else {
        return min_heap.top();
    }
}

private:
priority_queue max_heap; // 大根，保存较小的
priority_queue<int, vector, greater> min_heap;
};
打卡

0 赞同 0 条回复

言之命至普通 2024年3月30日上午9:37

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() {
        // 如果是偶数，两个堆顶元素相加/2.0
        if(min.size() == max.size()){
            return (min.peek() + max.peek()) / 2.0;
        } else {// 如果是奇数，大根堆顶元素
            return max.peek() * 1.0;
        }
    }
}

0 赞同 0 条回复

紫芝普通 2024年3月29日下午12:53

思路：大顶堆＋小顶堆
时间复杂度：o(logn)
空间复杂度：o(n)

“`c++
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {

}

void addNum(int num) {
    if (small_heap.size() != big_heap.size()) {
        small_heap.push(num);
        big_heap.push(small_heap.top());
        small_heap.pop();
    } else {
        // s == b, insert in small heap first.
        big_heap.push(num);
        small_heap.push(big_heap.top());
        big_heap.pop();
    }
}

double findMedian() {
    return small_heap.size() != big_heap.size() ? small_heap.top() : (small_heap.top() + big_heap.top())/2.0;
}

private:
priority_queue<int, vector, greater> small_heap;
priority_queue<int, vector, less> big_heap;
};

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

“`

0 赞同 0 条回复

heathhou 普通 2024年3月27日下午10:14

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

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

    double findMedian() {
        if(min.size() == max.size()){
            return (min.top() + max.top()) / 2.0;
        }
        else 
            return max.top();

    }

private:
    priority_queue<int> min;
    priority_queue<int, vector<int>, greater<int>> max;
};

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

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

0 赞同 0 条回复

云无深雁影普通 2024年3月27日下午4:43

//使用队列实现 add时间复杂度On get时间复杂度O1
class MedianFinder {
LinkedList small,big;
LinkedList mid;
/** initialize your data structure here. */
public MedianFinder() {
small = new LinkedList();
mid = new LinkedList();
big = new LinkedList();
}

public void addNum(int num) {
    if(mid.isEmpty()){
        mid.add(num);
        return;
    }
    int midsmall = mid.getFirst();
    int midbig = mid.getLast();
    if(num < midsmall){
        small.add(num);
        mid.addFirst(findBiggest(small));
    }else if(num >midbig){
        big.add(num);
        mid.addLast(findSmallest(big));
    }else{//在中间
        int temp = mid.removeLast();
        mid.addLast(num);
        mid.addLast(temp);
    }
    while(mid.size() ==3 || small.size()!=big.size() ){
        if(mid.size()==3 || small.size() < big.size()){
            small.add(mid.removeFirst());
        }else if(small.size() > big.size()){
            big.add(mid.removeLast());
        }
    }
}
private int findSmallest(LinkedList<Integer> set){
    int smallest = Integer.MAX_VALUE;
    int smallestLoc = 0;
    for(int i = 0; i < set.size(); i++){
        if(set.get(i) < smallest){
            smallest = set.get(i);
            smallestLoc = i;
        }
    }
    set.remove(smallestLoc);
    return smallest;
}
private int findBiggest(LinkedList<Integer> set){
    int biggest = Integer.MIN_VALUE;
    int biggestLoc = 0;
    for(int i = 0; i < set.size(); i++){
        if(set.get(i) > biggest){
            biggest = set.get(i);
            biggestLoc = i;
        }
    }
    set.remove(biggestLoc);
    return biggest;
}

public double findMedian() {
    if(mid.size() == 0)
        return 0.5 * (findBiggest(small) + findSmallest(big));
    if(mid.size() == 1)
        return mid.getFirst();
    if(mid.size() == 2)
        return 0.5 * (mid.getFirst() + mid.getLast());
    return -1;
}

}

//使用堆 add时间复杂度降到Ologn
class MedianFinder {
Queue small,big;
/** initialize your data structure here. */
public MedianFinder() {
big = new PriorityQueue();
small = new PriorityQueue<>((a,b)->(b-a));
}
public void addNum(int num) {
if(small.isEmpty() || big.isEmpty())
small.add(num);
else{
int smallBiggest = small.peek();
int bigsmallest = big.peek();
if(num > bigsmallest){
big.add(num);
}else {
small.add(num);
}
}
while(small.size() > big.size() + 1){
big.add(small.remove());
}
while(small.size() < big.size()){
small.add(big.remove());
}

}    
public double findMedian() {
    if(small.size() == big.size()){
        return (small.peek() + big.peek())*0.5;
    }
    else    
        return small.peek();
}

}

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月27日上午11:41

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(max.size() == min.size()){
            min.add(num);
            max.add(min.poll());

        //奇变偶
        }else{
            max.add(num);
            min.add(max.poll());
        }
    }

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

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

空间复杂度：O(n)

0 赞同 0 条回复

Jimmy 普通 2024年3月27日上午11:41

建立一个大顶堆（元素从大到小排列，堆顶元素最小），一个小顶堆（元素从小到大排列，堆顶元素最大），始终保持A的元素大于等于B的元素，个数为偶数时中位数为两个堆顶元素和的一半，为奇数时中位数为A的堆顶元素
1. 时间复杂度：
1. 查找中位数 O(1)：获取堆顶元素使用 O(1) 时间；
2. 添加数字 O(log⁡N) ：堆的插入和弹出操作使用 O(log⁡N) 时间。
2. 复杂度 O(N) ：其中 N 为数据流中的元素数量，小顶堆 A和大顶堆 B 最多同时保存 N 个元素

class MedianFinder {
public:
    priority_queue<int,vector<int>,greater<int>> A;// A是小顶堆，里面的元素是从大到小排列
    priority_queue<int,vector<int>,less<int>> B;//B是大顶堆，里面的元素是从小到大排列

    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        if(A.size() != B.size())//要往B里面插入元素，因为B中的元素是从小到大排列，插入的元素应该先经过A，将A中的顶部元素（也就是A里面的最小元素）放到B里面
        {
            A.push(num);
            B.push(A.top());
            A.pop();
        }
        else// 要往A里面插
        {
            B.push(num);
            A.push(B.top());
            B.pop();
        }
    }

    double findMedian() {
        return A.size() == B.size() ? (A.top()+B.top())/2.0 : A.top();
    }
};

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

0 赞同 0 条回复

一个达不刘普通 2024年3月27日上午11:11

class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue<int, vector, greater> A;//小根堆，保存较大的一半
priority_queue<int, vector, less> B;//小根堆，保存较大的一半
MedianFinder() {}

void addNum(int num) {
    if(A.size()!=B.size()){
        A.push(num);
        B.push(A.top());//保持两个堆长度一致性。Apush，Apop
        A.pop();
    }else{
        B.push(num);
        A.push(B.top());
        B.pop();
    }
}

double findMedian() {
    if(A.size()!=B.size()){
        return A.top();
    }else{
        return (A.top()+B.top()) /2.0 ;
    }
}

};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月27日上午9:13

打卡

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        _size = 0;
    }

    void addNum(int num) {
        if(_size % 2 == 0) {
            pqMax.push(num);
            pqMin.push(pqMax.top());
            pqMax.pop();
        } else {
            pqMin.push(num);
            pqMax.push(pqMin.top());
            pqMin.pop();
        }
        _size++;
    }

    double findMedian() {
        if(_size % 2 == 0) {
            return (pqMax.top() + pqMin.top()) / 2.0;
        } else return pqMin.top() * 1.0;
    }
private:
    priority_queue<int, vector<int>, less<int>> pqMax;
    priority_queue<int, vector<int>, greater<int>> pqMin;
    int _size;

};

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

0 赞同 0 条回复

机电皮怪永久会员 2024年3月26日下午11:55

时间复杂度O(log(n)),空间复杂度O(n)

“`C++
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {

}

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

double findMedian() {
    if(min_heap.size() == max_heap.size())
    {
        return (min_heap.top() + max_heap.top()) / 2.0;
    }
    else 
    {
        return max_heap.top();
    }
}

private:
priority_queue min_heap; //小根堆保留大的
priority_queue<int, vector, greater> max_heap; //大根堆保留小的
};

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

“`

0 赞同 0 条回复

王位詮釋普通 2024年3月26日下午9:03

自己写的，借助list，虽然过了，但是效率不好：
class MedianFinder {
    List<Integer> list;
    /** initialize your data structure here. */
    public MedianFinder() {
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        list.add(num);
        Collections.sort(list);
    }

    public double findMedian() {
        int length = list.size();
        if((length&1)==1){
            return list.get(length/2);
        }else{
            return (list.get(length/2-1)+list.get(length/2))/2.0;
        }
    }
}
堆：
class MedianFinder {
    Queue<Integer> min;//大根堆
    Queue<Integer> 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;
        }
    }
}

0 赞同 0 条回复

Raphtalia. 普通 2024年3月26日下午8:51

class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue mi;//大根堆
priority_queue<int,vector,greater> ma;//小根堆
MedianFinder() {

}

void addNum(int num) {
    mi.push(num);
    ma.push(mi.top());
    mi.pop();
    if(ma.size() > mi.size()) {
        mi.push(ma.top());
        ma.pop();
    } 
}

double findMedian() {
    if(mi.size() == ma.size()) return (double)(mi.top() + ma.top()) / 2;
    else return (double) mi.top();
}

};

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
时间复杂度O（NLOGN），空间复杂度O(N)

0 赞同 0 条回复

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

共以下 13 个回答

# 回答此问题取消回复

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

共以下 13 个回答

# 回答此问题 取消回复

# 回答此问题取消回复