每次获取中位数前进行排序
java
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class MedianFinder1 { private List<Integer> data; public MedianFinder1() { data = new ArrayList<>(); } // 插入数字到数据流 public void Insert(Integer num) { data.add(num); // 每次插入后排序，保持列表有序 Collections.sort(data); } // 获取当前数据流的中位数 public Double GetMedian() { int size = data.size(); if (size == 0) return 0.0; if (size % 2 == 1) { // 奇数个元素，返回中间值 return (double) data.get(size / 2); } else { // 偶数个元素，返回中间两个数的平均值 int mid = size / 2; return (data.get(mid - 1) + data.get(mid)) / 2.0; } } }- 插入操作：每次插入需要排序，时间复杂度O(n log n)
- 获取中位数：直接通过索引访问，时间复杂度O(1)
- 空间复杂度：O(n)，需要存储所有数据
插入排序法
在方法一基础上优化，在插入时就找到正确位置，避免每次都完整排序。同时利用二分查找找到插入位置，减少排序开销
java
import java.util.ArrayList; import java.util.List; public class MedianFinder2 { private List<Integer> data; public MedianFinder2() { data = new ArrayList<>(); } public void Insert(Integer num) { // 使用二分查找找到合适的插入位置 int left = 0, right = data.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (data.get(mid) < num) { left = mid + 1; } else { right = mid - 1; } } // 在找到的位置插入元素 data.add(left, num); } public Double GetMedian() { int size = data.size(); if (size == 0) return 0.0; if (size % 2 == 1) { return (double) data.get(size / 2); } else { int mid = size / 2; return (data.get(mid - 1) + data.get(mid)) / 2.0; } } }- 插入操作：二分查找O(log n) + 插入操作O(n) = O(n)
- 获取中位数：O(1)，通过索引直接访问
- 优化效果：比方法一有明显提升，特别适合部分有序的数据
双堆法
是最高效的解法，利用大顶堆和小顶堆的特性来动态维护中位数，使用大顶堆存较小一半，小顶堆存较大一半
⽤⼀个数字来不断统计数据流中的个数，并且创建⼀个最⼤堆，⼀个最⼩堆
- 如果插⼊的数字的个数是奇数的时候，让最⼩堆⾥⾯的元素个数⽐最⼤堆的个数多 1 ，这样⼀来中位数就是⼩顶堆的堆顶
- 如果插⼊的数字的个数是偶数的时候，两个堆的元素保持⼀样多，中位数就是两个堆的堆顶的元素相加除以2 。
java
public class Solution { private int count = 0; private PriorityQueue<Integer> min = new PriorityQueue<Integer>(); private PriorityQueue<Integer> max = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer o1, Integer o2) { return o2 - o1; } }); public void Insert(Integer num) { count++; if (count % 2 == 1) { // 奇数的时候，需要最⼩堆的元素⽐最⼤堆的元素多⼀个。 // 先放到最⼤堆⾥⾯，然后弹出最⼤的 max.offer(num); // 把最⼤的放进最⼩堆 min.offer(max.poll()); } else { // 放进最⼩堆 min.offer(num); // 把最⼩的放进最⼤堆 max.offer(min.poll()); } } public Double GetMedian() { if (count % 2 == 0) { return (min.peek() + max.peek()) / 2.0; } else { return (double) min.peek(); } } }- 插入操作：堆的插入操作O(log n)，平衡操作O(log n)，总体O(log n)
- 获取中位数：直接访问堆顶元素，O(1)时间复杂度