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

lQl 永久会员 2025年1月16日下午5:30

class MedianFinder {
    Queue<Integer> A,B;
    /** initialize your data structure here. */
    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() {
        if(A.size()!=B.size()){
            return A.peek();
        }else{
            return (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();
 */

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

0 赞同 0 条回复

Xiang. 永久会员 2024年12月22日下午4:03

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() {
        return min.size()!=max.size()?max.peek():(max.peek()+min.peek())/2.0;
    }
}
时间复杂度：O（logn）
空间复杂度：O（n）

0 赞同 0 条回复

陆狗陆狗普通 2024年12月20日下午10:39

解题思路
– 如果是通过数组维护底层（有序），添加元素后其他元素要后移，时间复杂度是O(n)
– 如果是通过2个堆（大顶堆和小顶堆）来维护底层，添加元素的时间复杂度是O(Logn)
– 具体如何维护这2个堆呢？
– 把数组分成2部分，左边是小的一部分，右边是大的一部分。右边最小的元素>=左边最大的元素
– 左边是大顶堆，右边是小顶堆。如果2边的数量相同，优先把多的那个放在右边。
– 放的过程很讲究，比如要把元素最终放在右边，不能直接放在右边，而是先放在左边之后取出左边的堆顶元素，把这个元素放在右边。想把元素最终放在左边也是类似的。（为什么要这样做？是为了维护性质“右边最小的元素>=左边最大的元素”）
【题解1】

class MedianFinder {

    // PriorityQueue默认是小顶堆
    Queue<Integer> right = new PriorityQueue<>();
    // 【错误点】大顶堆的写法
    Queue<Integer> left = new PriorityQueue<>((v1, v2) -> (v2 - v1));

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

    }

    public void addNum(int num) {
        // 如果是通过数组维护底层，添加元素后其他元素要后移，时间复杂度是O(N)
        // 如果是通过堆来维护底层，添加元素的时间复杂度是O(LogN)
        // 把数组分成2部分，左边是小的一部分，右边是大的一部分。右边最小的元素>=左边最大的元素
        // 左边是大顶堆，右边是小顶堆。如果2边的数量相同，优先把多的那个放在右边。
        // 放的过程很讲究，比如要把元素最终放在右边，不能直接放在右边，而是先放在左边之后取出左边的堆顶元素，把这个元素放在右边。想把元素最终放在左边也是类似的。
        // 为什么要这样做？是为了维护性质“右边最小的元素>=左边最大的元素”
        if (right.size() == left.size()) {
            // 最终要放在右边，但是要先放到左边过一下
            left.offer(num);
            right.offer(left.poll());
        } else {
            right.offer(num);
            left.offer(right.poll());
        }
    }

    public double findMedian() {
        if (right.size() == left.size()) {
            // 取堆顶数据的平均
            // 【改进写法】（right.peek()+right.peek()）/ 2.0
            return ((double) right.peek() + (double) right.peek())) / 2;
        } else {
            // 否则取右边的数据（多余的1个数据优先放在右边）
            return (double) right.peek();
        }
    }
}

错误点1：大顶堆的写法，默认的优先队列是小顶堆。声明大顶堆需要传入比较器，把v1和v2的值比较取反。
优化点2：（right.peek()+right.peek()）/ 2.0，只需要除以2.0就不会向下取整了，而是返回小数了。

0 赞同 0 条回复

Kisara 普通 2024年12月18日下午6:07

大小顶堆

class MedianFinder {
    PriorityQueue<Integer> A;
    PriorityQueue<Integer> 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()){
            B.offer(num);
            A.offer(B.poll());
        }else {
            A.offer(num);
            B.offer(A.poll());
        }
    }


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

0 赞同 0 条回复

jaron 普通 2024年12月17日下午8:58

class MedianFinder {

    PriorityQueue<Integer> min, max;

    /** initialize your data structure here. */
    public MedianFinder() {
        // 较大的一半放小顶堆
        min = new PriorityQueue<Integer>((a, b) -> (a - b));
        // 较小的一半放大顶堆
        max = new PriorityQueue<Integer>((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 (double) max.peek();
        }
    }
}

0 赞同 0 条回复

苯庸普通 2024年12月17日下午8:35

class MedianFinder {

List<Integer> list;

public MedianFinder() {
    list = new ArrayList();
}

public void addNum(int num) {
    int i = 0;
    while(i < list.size()){
        if(list.get(i) > num){
            break;
        }
        i++;
    }
    list.add(i, num);
}

public double findMedian() {
    if(list.size() % 2 == 1){
        return list.get(list.size()/2) / 1.0;
    }
    return (list.get(list.size()/2) + list.get(list.size()/2-1)) / 2.0;
}

}
思路：插入排序
时间：O（n）
空间：O（n）

0 赞同 0 条回复

秋山丽奈普通 2024年12月17日下午8:26

思路：构造大顶堆 + 小顶堆 Java 使用 PriorityQueue 可实现小顶堆

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

Aatorx 永久会员 2024年12月17日下午4:16

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

    }

    void addNum(int num) {
        if (A.size() == B.size()) {
            B.push(num);
            A.push(B.top());
            B.pop();
        }else {
            A.push(num);
            B.push(A.top());
            A.pop();
        }
    }
    double findMedian() {
        if (A.size() == B.size()){
            return (A.top() + B.top()) / 2.0;
        }else {
            return A.top();
        }
    }
};

分别用大顶堆保存较小的数据，小顶堆保存较大的数据，堆顶的元素即为中位数。
时间复杂度：查找中位数O(1)，添加元素O(longN)，空间复杂度O(N)。

0 赞同 0 条回复

月下足迹普通 2024年12月17日上午11:08

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()) {
            B.add(num);
            A.add(B.poll());
        }else {
            A.add(num);
            B.add(A.poll());
        }
    }
    public double findMedian() {
        return A.size() == B.size()? (A.peek() + B.peek()) / 2.0 : A.peek();
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年12月16日下午9:51

/**
 * 中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 * 
 * 题意解读：中位数的求法：
 *      如果有序列表的个数是奇数，返回中间的值
 *      如果有序列表的个数是偶数，返回中间的两个值的平均值
 * 方法一：优先级队列实现
 *      维护两个优先级队列，一个用于记录较小的数，一个用于记录较大的数
 *      小顶堆 A：保存较大的数，长度为 N / 2（N 为偶数） 或 (N + 1) / 2（N 为奇数）
 *      大顶堆 B：保存较小的数，长度为 N / 2（N 为偶数） 或 (N - 1) / 2（N 为奇数）
 *      中位数可仅根据 A,B 的堆顶元素计算得到。
 *      设 A 的个数为 m，B 的个数为 n。
 *      当 m == n 时，向 A 中添加元素，即：先将元素添加至 B 中，再将 B 堆顶的元素添加到 A 中即可
 *      当 m != n 时，A 的数量多，向 B 中添加元素，即：先将元素添加到 A 中，再将 A 堆顶的元素添加到 B 中。
 * 
 *  中位数求解：
 *      m == n 时，A、B 的堆顶元素求平均值
 *      m != n 时，A 堆顶元素就是中位数（因为添加元素过程始终保持着 m >= n）
 */
class MedianFinder {
    PriorityQueue<Integer> A, B;

    /** initialize your data structure here. */
    public MedianFinder() {
        // 小顶堆，保存较大的元素
        A = new PriorityQueue<>();
        // 大顶堆，保存较小的元素
        B = new PriorityQueue<>((a, b) -> (b - a));
    }

    public void addNum(int num) {
        if (A.size() == B.size()) {
            // m == n，先将元素添加至 B，再将 B 的堆顶元素存入到 A 中
            B.add(num);
            A.add(B.poll());
        } else {
            // m != n，先将元素添加至 A，再将 A 堆顶元素存入到 B 中
            A.add(num);
            B.add(A.poll());
        }
    }

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

0 赞同 0 条回复

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

共以下 10 个回答

# 回答此问题取消回复

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复