题解 | #数据流中的中位数#
数据流中的中位数
http://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1
题目主要信息：
- 寻找数据的中位数
- 数据量在不断输入增长
举一反三：
学习完本题的思路你可以解决如下题目：
方法一：插入排序法（推荐使用）
知识点：插入排序
插入排序是排序中的一种方式，一旦一个无序数组开始排序，它前面部分就是已经排好的有序数组（一开始长度为0），而其后半部分则是需要排序的无序数组，插入排序的做法就是遍历后续需要排序的无序部分，对于每个元素，插入到前半部分有序数组中属于它的位置——即最后一个小于它的元素后。
思路：
传统的寻找中位数的方法便是排序之后，取中间值或者中间两位的平均即可。但是这道题因为数组在不断增长，每增长一位便需要排一次，很浪费时间，于是可以考虑在增加数据的同时将其有序化，这个过程就让我们想到了插入排序：对于每个输入的元素，遍历已经有序的数组，将其插入到属于它的位置。
int i = 0;
//遍历找到插入点
for(; i < val.size(); i++){
if(num <= val.get(i))
break;
}
//插入相应位置
val.add(i, num);
具体做法：
- step 1：用一数组存储输入的数据流。
- step 2：Insert函数在插入的同时，遍历之前存储在数组中的数据，按照递增顺序依次插入，如此一来，加入的数据流便是有序的。
- step 3：GetMedian函数可以根据下标直接访问中位数，分为数组为奇数个元素和偶数个元素两种情况。记得需要类型转换为double。
Java实现代码：
import java.util.*;
public class Solution {
private ArrayList<Integer> val = new ArrayList<Integer>();
public void Insert(Integer num) {
if(val.isEmpty())
//val中没有数据，直接加入
val.add(num);
//val中有数据，需要插入排序
else{
int i = 0;
//遍历找到插入点
for(; i < val.size(); i++){
if(num <= val.get(i))
break;
}
//插入相应位置
val.add(i, num);
}
}
public Double GetMedian() {
int n = val.size();
//奇数个数字
if(n % 2 == 1)
//类型转换
return (double)val.get(n / 2);
//偶数个数字
else{
double a = val.get(n / 2);
double b = val.get(n / 2 - 1);
return (a + b) / 2;
}
}
}
C++实现代码：
class Solution {
public:
//记录输入流
vector<int> val;
void Insert(int num) {
if(val.empty())
//val中没有数据，直接加入
val.push_back(num);
//val中有数据，需要插入排序
else{
int i = 0;
//遍历找到插入点
for(; i < val.size(); i++){
if(num <= val[i]){
break;
}
}
val.insert(val.begin() + i, num);
}
}
double GetMedian() {
int n = val.size();
//奇数个数字
if(n % 2 == 1){
//类型转换
return double(val[n / 2]);
}
//偶数个数字
else{
double a = val[n / 2];
double b = val[n / 2 - 1];
return (a + b) / 2;
}
}
};
Python代码实现：
class Solution:
def __init__(self):
self.val = []
def Insert(self, num):
if len(self.val) == 0:
#val中没有数据，直接加入
self.val.append(num)
#val中有数据，需要插入排序
else:
i = 0
#遍历找到插入点
while i < len(self.val):
if num <= self.val[i]:
break
i = i + 1
#插入相应位置
self.val.insert(i, num)
def GetMedian(self):
n = len(self.val)
#奇数个数字
if n % 2 == 1:
#类型转换
return self.val[n // 2]
#偶数个数字
else:
return (self.val[n // 2] + self.val[n // 2 - 1]) / 2.0
复杂度分析：
- 时间复杂度：Insert函数，不管遍历还是插入都是，GetMedian函数，直接访问
- 空间复杂度：，记录输入流的数组
方法二：堆排序（扩展思路）
知识点：优先队列
优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是，而每次取出堆顶元素都是直接取出。
思路：
除了插入排序，我们换种思路，因为插入排序每次要遍历整个已经有的数组，很浪费时间，有没有什么可以找到插入位置时能够更方便。
我们来看看中位数的特征，它是数组中间个数字或者两个数字的均值，它是数组较小的一半元素中最大的一个，同时也是数组较大的一半元素中最小的一个。那我们只要每次维护最小的一半元素和最大的一半元素，并能快速得到它们的最大值和最小值，那不就可以了嘛。这时候就可以想到了堆排序的优先队列。
具体做法：
- step 1：我们可以维护两个堆，分别是大顶堆min，用于存储较小的值，其中顶部最大；小顶堆max，用于存储较大的值，其中顶部最小，则中位数只会在两个堆的堆顶出现。
- step 2：我们可以约定奇数个元素时取大顶堆的顶部值，偶数个元素时取两堆顶的平均值，则可以发现两个堆的数据长度要么是相等的，要么奇数时大顶堆会多一个。
- step 3：每次输入的数据流先进入大顶堆排序，然后将小顶堆的最大值弹入大顶堆中，完成整个的排序。
- step 4：但是因为大顶堆的数据不可能会比小顶堆少一个，因此需要再比较二者的长度，若是小顶堆长度小于大顶堆，需要从大顶堆中弹出最小值到大顶堆中进行平衡。
图示：
Java实现代码：
import java.util.*;
public class Solution {
//小顶堆，元素数值都比大顶堆大
private PriorityQueue<Integer> max = new PriorityQueue<>();
//大顶堆，元素数值较小
private PriorityQueue<Integer> min = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
//维护两个堆，取两个堆顶部即与中位数相关
public void Insert(Integer num) {
//先加入较小部分
min.offer(num);
//将较小部分的最大值取出，送入到较大部分
max.offer(min.poll());
//平衡两个堆的数量
if(min.size() < max.size())
min.offer(max.poll());
}
public Double GetMedian() {
//奇数个
if(min.size() > max.size())
return (double)min.peek();
else
//偶数个
return (double)(min.peek() + max.peek()) / 2;
}
}
C++实现代码：
class Solution {
public:
//大顶堆，元素数值较小
priority_queue<int> min;
//小顶堆，元素数值都比大顶堆大
priority_queue<int, vector<int>, greater<int>> max;
//维护两个堆，取两个堆顶部即可
void Insert(int num) {
//先加入较小部分
min.push(num);
//将较小部分的最大值取出，送入到较大部分
max.push(min.top());
min.pop();
//平衡两个堆的数量
if(min.size() < max.size()){
min.push(max.top());
max.pop();
}
}
double GetMedian() {
//奇数个
if(min.size() > max.size())
return (double)min.top();
else
//偶数个
return (double)(min.top() + max.top()) / 2;
}
};
Python代码实现：
import heapq
class Solution:
def __init__(self):
#小顶堆，元素数值都比大顶堆大
self.max = []
#大顶堆，元素数值较小，加入元素要乘-1才能实现大顶堆，取出时也要乘-1还原
self.min = []
def Insert(self, num):
#先加入较小部分
heapq.heappush(self.min, (-1 * num))
#将较小部分的最大值取出，送入到较大部分
heapq.heappush(self.max, -1 * self.min[0])
heapq.heappop(self.min)
#平衡两个堆的数量
if len(self.min) < len(self.max):
heapq.heappush(self.min, -1 * self.max[0])
heapq.heappop(self.max)
def GetMedian(self):
#奇数个
if len(self.min) > len(self.max):
return self.min[0] * -1.0
else:
#偶数个
return (-1 * self.min[0] + self.max[0]) / 2
复杂度分析
- 时间复杂度：Insert函数，维护堆的复杂度，GetMedian函数，直接访问
- 空间复杂度：，两个堆的空间，虽是两个，但是一个堆最多
