[剑指offer]面试题第[41]题[Leetcode][第235题][JAVA][数据流中的中位数][优先队列][堆]

ゝ一世哀愁。 2023-03-01 05:49 143阅读 0赞

#### 【问题描述】\[困难\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 思路1 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]

**时间复杂度：O(logN) 空间复杂度：O(N)**

import java.util.PriorityQueue;
    
    public class MedianFinder { 
    
        /** * 当前大顶堆和小顶堆的元素个数之和 */
        private int count;
        private PriorityQueue<Integer> maxheap;
        private PriorityQueue<Integer> minheap;
    
        /** * initialize your data structure here. */
        public MedianFinder() { 
            count = 0;
            //maxHeap = new PriorityQueue<>(Collections.reverseOrder());
            maxheap = new PriorityQueue<>((x, y) -> y - x);
            minheap = new PriorityQueue<>();
        }
    
        public void addNum(int num) { 
            count += 1;
            maxheap.offer(num);
            minheap.add(maxheap.poll());
            // 如果两个堆合起来的元素个数是奇数，小顶堆要拿出堆顶元素给大顶堆
            if ((count & 1) != 0) { 
                maxheap.add(minheap.poll());
            }
            /* //如果不平衡则调整 不用count if (minHeap.size() > maxHeap.size()) { maxHeap.offer(minHeap.poll()); } */
        }
    
        public double findMedian() { 
            if ((count & 1) == 0) { 
                // 如果两个堆合起来的元素个数是偶数，数据流的中位数就是各自堆顶元素的平均值
                return (double) (maxheap.peek() + minheap.peek()) / 2;
            } else { 
                // 如果两个堆合起来的元素个数是奇数，数据流的中位数大顶堆的堆顶元素
                return (double) maxheap.peek();
            }
    //不用count
    public double findMedian() { 
            if (maxHeap.size() == minHeap.size()) { 
                return (maxHeap.peek() + minHeap.peek()) * 0.5;
            }
            return maxHeap.peek();
        }
    
    
    
    
        }
    }

###### 2. 思路2 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 7]

**复杂度**  
![在这里插入图片描述][20200722153721797.png]

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

#### 【总结】 ####

###### 1.最大堆/最小堆初始化 ######

**最小堆**  
PriorityQueue minheap = new PriorityQueue<>();  
**最大堆**  
PriorityQueue maxheap = new PriorityQueue<>((x, y) -> y - x);  
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());

###### 2.找规律 模拟过程 不可能是一蹴而就 而是多次失败后才能找到的规律和转移过程 ######

转载链接：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/you-xian-dui-lie-python-dai-ma-java-dai-ma-by-liwe/

参考链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solution/you-xian-dui-lie-wu-fei-hua-jian-dan-yi-dong-by-je/

参考链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solution/mian-shi-ti-41-shu-ju-liu-zhong-de-zhong-wei-shu-y/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/e6fbe359b9d44b40b0f6d89268fe58e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230209/1107443c784d4893a1ec613b4482f5d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20230209/595bda37d48148d1921b4664a942b35b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20230209/044bdff0dc484c8d9e94bbeedd31f5ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: /images/20230209/9890b36d8903485898372186117d2819.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]: /images/20230209/172a7338826a4ae18023a7cf366425a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]: /images/20230209/bec5f9a193f041a2b0bee71d28ff2dc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 7]: /images/20230209/9a5f1d6aeeb444e28d70d5999b8241ba.png
[20200722153721797.png]: https://img-blog.csdnimg.cn/20200722153721797.png