每次获取中位数前进行排序javaimport java.util.ArrayList; import java.util.Collections; import java.util.List; public class MedianFinder1 { private ListInteger 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)需要存储所有数据插入排序法在方法一基础上优化在插入时就找到正确位置避免每次都完整排序。同时利用二分查找找到插入位置减少排序开销javaimport java.util.ArrayList; import java.util.List; public class MedianFinder2 { private ListInteger 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 。javapublic class Solution { private int count 0; private PriorityQueueInteger min new PriorityQueueInteger(); private PriorityQueueInteger max new PriorityQueueInteger(new ComparatorInteger() { 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)时间复杂度