题解 | #数据流中的中位数#

数据流中的中位数

http://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

题目主要信息:
  • 寻找数据的中位数
  • 数据量在不断输入增长
举一反三:

学习完本题的思路你可以解决如下题目:

BM46. 最小的k个数

方法一:插入排序法(推荐使用)

知识点:插入排序

插入排序是排序中的一种方式,一旦一个无序数组开始排序,它前面部分就是已经排好的有序数组(一开始长度为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函数O(n)O(n),不管遍历还是插入都是O(n)O(n),GetMedian函数O(1)O(1),直接访问
  • 空间复杂度:O(n)O(n),记录输入流的数组
方法二:堆排序(扩展思路)

知识点:优先队列

优先队列即PriorityQueue,是一种内置的机遇堆排序的容器,分为大顶堆与小顶堆,大顶堆的堆顶为最大元素,其余更小的元素在堆下方,小顶堆与其刚好相反。且因为容器内部的次序基于堆排序,因此每次插入元素时间复杂度都是O(log2n)O(log_2n),而每次取出堆顶元素都是直接取出。

思路:

除了插入排序,我们换种思路,因为插入排序每次要遍历整个已经有的数组,很浪费时间,有没有什么可以找到插入位置时能够更方便。

我们来看看中位数的特征,它是数组中间个数字或者两个数字的均值,它是数组较小的一半元素中最大的一个,同时也是数组较大的一半元素中最小的一个。那我们只要每次维护最小的一半元素和最大的一半元素,并能快速得到它们的最大值和最小值,那不就可以了嘛。这时候就可以想到了堆排序的优先队列。

具体做法:

  • 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函数O(log2n)O(log_2n),维护堆的复杂度,GetMedian函数O(1)O(1),直接访问
  • 空间复杂度:O(n)O(n),两个堆的空间,虽是两个,但是一个堆最多n/2n/2
全部评论
我实在是无语了,最关键的文字部分tm写反了可还行, step 3:每次输入的数据流先进入大顶堆排序,然后将大顶堆的最大值弹入小顶堆中,完成整个的排序。
5 回复 分享
发布于 2022-06-30 18:04
大顶堆的最大值谈入小顶堆吧
点赞 回复 分享
发布于 2022-05-25 19:43
教材也好网上的教程也好,为什么一到关键部分就一堆错字
点赞 回复 分享
发布于 2022-06-28 21:30
每一次插入还要计算两个堆的大小,这就是n方复杂度了已经
点赞 回复 分享
发布于 2022-09-21 15:26 陕西
step3和step4的大小写反的有点多啊
点赞 回复 分享
发布于 2022-11-23 17:10 上海
这答案根本没法看,步骤一堆说反的
点赞 回复 分享
发布于 2023-10-13 17:10 广东

相关推荐

拉丁是我干掉的:把上海理工大学改成北京理工大学。成功率增加200%
点赞 评论 收藏
分享
totoroyyw:千年老妖😂
投递华为等公司10个岗位
点赞 评论 收藏
分享
评论
22
3
分享
牛客网
牛客企业服务