九号球普通 2023年11月29日上午8:45

“`java
class MedianFinder {
//采用大顶堆和小顶堆，A为大，B为小，偶数时，两个堆存放元素数相同，奇数时A存放多一个，则中位数为A堆顶和B堆顶之和除以2，或者是A的堆顶
Queue A,B;
/** initialize your data structure here. */
public MedianFinder() {
//存放较小的一半
A = new PriorityQueue<>((x, y) -> (y – x));
//小顶堆存放较大的一半
B = new PriorityQueue<>();
}

public void addNum(int num) {
    if (A.size() == B.size()) {
        B.offer(num);
        A.offer(B.poll());
    } else {
        A.offer(num);
        B.offer(A.poll());
    }
}

public double findMedian() {
    if (A.size() == B.size()) {
        return (A.peek() + B.peek())/2.0;
    }
    return A.peek();
}

}

0 赞同 0 条回复

招舟子普通 2023年9月8日下午4:50

class MedianFinder {
Queue 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.offer(num);
        max.offer(min.poll());
    }else{
        max.offer(num);
        min.offer(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 条回复

屠龙手段普通 2023年8月24日下午9:07

优先队列

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.heap_min = []
        self.heap_max = []

    def addNum(self, num: int) -> None:

        if len(self.heap_min) == len(self.heap_max):
            heapq.heappush(self.heap_min, -heapq.heappushpop(self.heap_max, num))
        else:
            heapq.heappush(self.heap_max, -heapq.heappushpop(self.heap_min, -num))

    def findMedian(self) -> float:
        return -self.heap_min[0] if len(self.heap_max) != len(self.heap_min) else (self.heap_max[0] - self.heap_min[0]) / 2


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

0 赞同 0 条回复

BOZ 普通 2023年7月19日下午4:29

【思路】利用大小堆数据结构（具体是C++STL priority queue）分别保存一半的数据，大堆保存小数，小堆保存大数
【复杂度】时间复杂度O(nlogn)，空间复杂度O(n)，查找时间复杂度为O(1)

class MedianFinder {
    std::priority_queue<int> max_stack;
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_stack;

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

    void addNum(int num) {
        if (min_stack.size() == max_stack.size()) {
            min_stack.push(num);
            // printf("min top: %d\n", min_stack.top());
            max_stack.push(min_stack.top());
            min_stack.pop();
        } else {
            max_stack.push(num);
            // printf("max top: %d\n", max_stack.top());
            min_stack.push(max_stack.top());
            max_stack.pop();
        } 
    }

    double findMedian() {
        // printf("min num %lu, max num %lu\n", min_stack.size(), max_stack.size());
        // printf("min top %d, max top %d\n", min_stack.top(), max_stack.top());
        if (min_stack.size() == max_stack.size())
            return double(min_stack.top() + max_stack.top()) / 2;
        else 
            return max_stack.top();
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:45

“`C++
class MedianFinder {
public:
void addNum(int num) {
// 先将数字插入最大堆，再将最大堆顶部元素移动到最小堆
maxHeap.push(num);
minHeap.push(maxHeap.top());
maxHeap.pop();

    // 如果最大堆的元素比最小堆的元素多，则将最小堆顶部元素移动到最大堆
    if (maxHeap.size() < minHeap.size()) {
        maxHeap.push(minHeap.top());
        minHeap.pop();
    }
}

double findMedian() {
    // 如果最大堆和最小堆的元素个数相同，则返回两个堆顶元素的平均值
    if (maxHeap.size() == minHeap.size()) {
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
    // 否则，返回最大堆的堆顶元素
    else {
        return maxHeap.top();
    }
}

private:
std::priority_queue<int, std::vector, std::less> maxHeap; // 最大堆存放左半部分元素
std::priority_queue<int, std::vector, std::greater> minHeap; // 最小堆存放右半部分元素
};

“`

0 赞同 0 条回复

局外人普通 2023年7月18日下午4:11

思想：利用两个堆，一个大根堆，一个小根堆，保持其数量基本一致
时间复杂度O(logn) 空间复杂度O(n)

class MedianFinder {

    private PriorityQueue<Integer> small;
    private PriorityQueue<Integer> large;

    /** initialize your data structure here. */
    public MedianFinder() {
        small = new PriorityQueue<>();
        large = new PriorityQueue<>((a, b)->{
            return b-a;
        });
    }

    public void addNum(int num) {
        if(small.size() >= large.size()){
            small.offer(num);
            large.offer(small.poll());
        }else{
            large.offer(num);
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if(large.size() < small.size()){
            return small.peek();
        }else if(large.size() > small.size()){
            return large.peek();
        }
        return (large.peek()+small.peek())/2.0;
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月16日下午3:31

利用堆排，小存大，大存小，所以堆顶是中位数

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

    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 条回复

哈哈哈哈开开心心普通 2023年7月16日上午8:34

class MedianFinder:

    def __init__(self):
        self.minHeap = []
        self.maxHeap = []

    def addNum(self, num: int) -> None:
        if len(self.minHeap) == len(self.maxHeap):
            heapq.heappush(self.minHeap, num)
            heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))
        else:
            heapq.heappush(self.maxHeap, - num)
            heapq.heappush(self.minHeap, - heapq.heappop(self.maxHeap))


    def findMedian(self) -> float:
        if len(self.minHeap) == len(self.maxHeap):
            return (self.minHeap[0] + (-self.maxHeap[0])) / 2
        else:
            return -self.maxHeap[0]



# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

maintain两个堆

0 赞同 0 条回复

花老爷普通 2023年7月15日下午5:03

官解优先队列

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

0 赞同 0 条回复

Vow the vow。普通 2023年7月15日上午11:56

参考大神的代码

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

    public void addNum(int num) {
        if(minHeap.size() != maxHeap.size()){
            minHeap.add(num);
            maxHeap.add(minHeap.poll());  // 往大顶堆添加元素
        }else{
            maxHeap.add(num);
            minHeap.add(maxHeap.poll()); // 往小顶堆添加元素
        }
    }

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

0 赞同 0 条回复

yxy 普通 2023年7月15日上午11:29

时间复杂度:查找 O(1) ,添加数字O(logN) 空间复杂度:O(N)

class MedianFinder {
    priority_queue<int, vector<int>, less<int>> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

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

    double findMedian() {
        if(maxHeap.size()==minHeap.size())
            return (maxHeap.top()+minHeap.top())/2.0;
        else
            return minHeap.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 条回复

Yodl. 普通 2023年7月14日下午9:41

//优先队列  时间复杂度:查找中位数 O(1) ,添加数字O(logN)  空间复杂度:O(N)
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;
    }
};

0 赞同 0 条回复

张开怀普通 2023年7月14日下午5:11

class MedianFinder{
public:
       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<int> min_heap;  // 小根，保存较大的
       priority_queue<int, vector<int>, greater<int>> max_heap;  // 大根，保存较小的
}；

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月14日下午4:08

class MedianFinder {

    PriorityQueue<Integer> left; //堆顶大
    PriorityQueue<Integer> right;//堆顶小

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

    public void addNum(int num) {
        if(right.size() == left.size()){
            right.offer(num);
            left.offer(right.poll());
        }else{
            left.offer(num);
            right.offer(left.poll());
        }
    }

    public double findMedian() {

        if(right.size() == left.size()){
            return (right.peek() + left.peek()) / 2.0;
        }
        return left.peek() * 1.0;
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年7月14日下午3:34

MY

优先队列

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int,vector<int>,greater<int>>_min;
    priority_queue<int,vector<int>> _max;
    int size=0;
    MedianFinder() {

    }

    void addNum(int num) {
        // 偶数个
        if((size&1) != 1){
            _min.push(num);
            _max.push(_min.top());
            _min.pop();
        }
        else{
            _max.push(num);
            _min.push(_max.top());
            _max.pop();
        }
        size++;
    }

    double findMedian() {
        // 奇数
        if((size&1)==1){
            return _max.top();
        }
        else{
            return (double)(_min.top()+_max.top())/2;
        }
    }
};

0 赞同 0 条回复

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

共以下 15 个回答

MY

# 回答此问题取消回复

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

共以下 15 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复