剑指offer-63、数据流中的中位数
<h2 id="题描述">题⽬描述</h2><p>如何得到⼀个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使⽤ Insert() ⽅法读取数据流，使⽤ GetMedian() ⽅法获取当前读取数据的中位数。</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="排序列表法">排序列表法</h3>
<p>维护一个列表，每次获取中位数前进行排序</p>
<pre><code class="language-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;
}
}
}
</code></pre>
<ul>
<li><strong>插入操作</strong>：每次插入需要排序，时间复杂度O(n log n)</li>
<li><strong>获取中位数</strong>：直接通过索引访问，时间复杂度O(1)</li>
<li><strong>空间复杂度</strong>：O(n)，需要存储所有数据</li>
</ul>
<h3 id="插入排序法">插入排序法</h3>
<p>在方法一基础上优化，在插入时就找到正确位置，避免每次都完整排序。同时利用二分查找找到插入位置，减少排序开销</p>
<pre><code class="language-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;
}
}
}
</code></pre>
<ul>
<li><strong>插入操作</strong>：二分查找O(log n) + 插入操作O(n) = O(n)</li>
<li><strong>获取中位数</strong>：O(1)，通过索引直接访问</li>
<li><strong>优化效果</strong>：比方法一有明显提升，特别适合部分有序的数据</li>
</ul>
<h3 id="双堆法">双堆法</h3>
<p>是最高效的解法，利用大顶堆和小顶堆的特性来动态维护中位数，使用大顶堆存较小一半，小顶堆存较大一半</p>
<p>⽤⼀个数字来不断统计数据流中的个数，并且创建⼀个最⼤堆，⼀个最⼩堆</p>
<ul>
<li>如果插⼊的数字的个数是奇数的时候，让最⼩堆⾥⾯的元素个数⽐最⼤堆的个数多 1 ，这样⼀来中位数就是⼩顶堆的堆顶</li>
<li>如果插⼊的数字的个数是偶数的时候，两个堆的元素保持⼀样多，中位数就是两个堆的堆顶的元素相加除以2 。</li>
</ul>
<pre><code class="language-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();
}
}
}
</code></pre>
<ul>
<li><strong>插入操作</strong>：堆的插入操作O(log n)，平衡操作O(log n)，总体O(log n)</li>
<li><strong>获取中位数</strong>：直接访问堆顶元素，O(1)时间复杂度</li>
<li><strong>空间复杂度</strong>：O(n)，需要存储所有数据</li>
</ul>
<p><strong>为什么这种方法有效？</strong></p>
<ul>
<li><strong>大顶堆</strong>（maxHeap）：存储数据流中<strong>较小的一半</strong>数字，堆顶是这一半中的最大值</li>
<li><strong>小顶堆</strong>（minHeap）：存储数据流中<strong>较大的一半</strong>数字，堆顶是这一半中的最小值</li>
<li><strong>平衡维护</strong>：确保两个堆的大小相差不超过1，这样中位数就只与两个堆顶有关</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19468596
頁:
[1]