剑指offer(C++)-JZ41:数据流中的中位数(算法-排序)

简介: 剑指offer(C++)-JZ41:数据流中的中位数(算法-排序)

题目描述:

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。


数据范围:数据流中数个数满足1≤n≤1000  ,大小满足1≤val≤1000


进阶: 空间复杂度O(n)  , 时间复杂度O(nlogn)  


示例:

输入:

[5,2,3,4,1,6,7,0,8]


返回值:

"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "


说明:

数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...

解题思路:

本题是排序题目。三种解题思路。


1)快速排序


      按顺序插入,获取中位数时进行快速排序,然后根据奇偶尺寸分情况输出结果。


      时间复杂度O(nlogn),空间复杂度O(n)。


2)插入排序


      基于插入排序思想,插入时先分析数据应该插入的位置,这样就能保持数据集合的有序性,获取中位数直接根据奇偶尺寸分情况输出结果。


      插入操作的时间复杂度为二分查找和移动数据的最大值,O(n),又因为进行了n次插入,所以时间复杂度最坏为O(n2),最好为O(n),空间复杂度O(n)。


3)堆排序


      用两个优先序列(大小顶堆)将整个数据分为大小两部分,维持动态平衡进行插入,获取中位数直接根据奇偶尺寸分情况,从大小顶堆的根获取数据计算即可。


      时间复杂度O(nlogn),空间复杂度O(n)。

测试代码:

1)快速排序

#include <algorithm>
class Solution {
public:
    vector<int> v;
    // 插入
    void Insert(int num)
    {
        v.emplace_back(num);
    }
    // 获取中位数
    double GetMedian()
    { 
        int size = int(v.size());
        sort(v.begin(), v.end());
        // 奇偶分情况讨论
        // 右移1位等于除以2
        if(size & 1){
            return double(v[size >> 1]);
        }
        else{
            return double(v[size >> 1] + v[(size - 1) >> 1]) / 2;
        }
    }
};

2)插入排序

#include <algorithm>
class Solution {
public:
    vector<int> v;
    // 插入
    void Insert(int num)
    {
        // 查找合适插入的位置
        auto idx = lower_bound(v.begin(), v.end(), num);
        v.insert(idx, num);
    }
    // 获取中位数
    double GetMedian()
    { 
        int size = int(v.size());
        // 奇偶分情况讨论
        // 右移1位等于除以2
        if(size & 1){
            return double(v[size >> 1]);
        }
        else{
            return double(v[size >> 1] + v[(size - 1) >> 1]) / 2;
        }
    }
};

3)堆排序

class Solution {
public:
    priority_queue<int> minp; // 大顶堆
    priority_queue<int, vector<int>, greater<int>> maxp; // 小顶堆
    // 插入
    void Insert(int num)
    {
        // 大顶堆中存放数据
        minp.push(num);
        // 取大顶堆中最大的值放入小顶堆中
        maxp.push(minp.top()); 
        minp.pop();
        // 平衡两堆数据数量
        if (minp.size() < maxp.size()){
            minp.push(maxp.top());
            maxp.pop();
        }
    }
    // 获取中位数
    double GetMedian()
    { 
        return minp.size() > maxp.size() ? static_cast<double>(minp.top()) : static_cast<double>(minp.top() + maxp.top()) / 2;
    }
};


相关文章
|
2天前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
23 10
|
2天前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
26 10
|
2天前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
23 7
|
2天前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
18 5
|
3天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
17 2
|
11天前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
9天前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
16天前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
35 4
|
3月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
855 0
高精度算法(加、减、乘、除,使用c++实现)
|
3月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
56 0