剑指Offer-数据流中的中位数
剑指Offer-数据流中的中位数
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
思路
思路一：
维护一个数组，每次加入后，进行排序，当总元素个数为奇数时，中位数就是数组中间的元素；当总元素个数为偶数时，中位数就是数组中间元素和前一个元素的平均数。
思路二：
- 维护一个大顶堆，一个小顶堆，且保证两点：
- 小顶堆里的元素全大于大顶堆里的元素；
- 两个堆个数的差值小于等于1；
- 当insert的数字个数为奇数时：使小顶堆个数比大顶堆多1；当insert的数字个数为偶数时，使大顶堆个数跟小顶堆个数一样；
- 当总元素个数为奇数时，中位数就是小顶堆堆顶；当总元素个数为偶数时，中位数就是两个个堆堆顶平均数。
代码实现
package Tree; import java.util.ArrayList; import java.util.Collections; import java.util.PriorityQueue; /** * 数据流中的中位数 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 */ public class Solution43 { ArrayList<Integer> list = new ArrayList<>(); // 大顶堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); // 小顶堆，并且大顶堆元素都大于小顶堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 当前数据流读入的元素个数 int N = 0; public static void main(String[] args) { Solution43 solution43 = new Solution43(); solution43.Insert_2(3); System.out.println(solution43.GetMedian_2()); solution43.Insert_2(4); System.out.println(solution43.GetMedian_2()); } /** * 维护两个堆，一个大顶堆、一个小顶堆 * * @param val */ public void Insert_2(Integer num) { // 插入要保证两个堆存于平衡状态 if (N % 2 == 0) { // N 为偶数的情况下插入到小顶堆。 // 因为大顶堆元素都要大于小顶堆，但是新插入的元素不一定比小顶堆元素来的大， // 因此需要先将元素插入小顶堆，然后利用小顶堆为大顶堆的特点，取出堆顶元素即为最大元素，此时插入大顶堆 maxHeap.offer(num); minHeap.offer(maxHeap.poll()); } else { minHeap.offer(num); maxHeap.offer(minHeap.poll()); } N++; } public Double GetMedian_2() { if (N % 2 == 0) { return (maxHeap.peek() + minHeap.peek()) / 2.0; } else { return (double) minHeap.peek(); } } /** * 维护数组，加入时排序 * * @param num */ public void Insert(Integer num) { list.add(num); Collections.sort(list); } public Double GetMedian() { int n = list.size(); if (n % 2 == 0) { return Double.valueOf((list.get(n / 2) + list.get(n / 2 - 1)) / 2.0); } else { return Double.valueOf(list.get(n / 2)); } } }
