动态求解中位数

绝地灬酷狼 2022-05-26 11:50 158阅读 0赞

题意是这样的，给你一个序列寻找中位数？

其实这个可以转化为TopK问题，但是假如这个数组不断的变化呢？这个时候可以考虑使用堆来解决。

这是一个很经典的问题，值得反思和学习。

参考这一道题[leetcode 295. Find Median from Data Stream 双优先级队列 + 中位数查找][leetcode 295. Find Median from Data Stream _ _]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    class MedianFinder 
    {
        priority_queue<long> small, large;
    public:
    
        void addNum(int num) 
        {
            small.push(num);
            large.push(-small.top());
            small.pop();
            if (small.size() < large.size()) 
            {
                small.push(-large.top());
                large.pop();
            }
        }
    
        double findMedian() 
        {
            return small.size() > large.size()
                ? small.top()
                : (small.top() - large.top()) / 2.0;
        }
    };

[leetcode 295. Find Median from Data Stream _ _]: https://blog.csdn.net/jackzhang_123/article/details/78121691

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关数据流中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数

╰+哭是因爲堅強的太久メ/ 2023年02月22日 08:26/ 0 赞/ 10 阅读

相关（LeetCode）Java 求解寻找两个正序数组的中位数

文章目录一、题解二、代码一三、代码二四、总结一、题解给定两个大小为 m 和 n 的正序（从小到大

- 日理万妓/ 2022年12月20日 02:53/ 0 赞/ 175 阅读

相关求解中位数

找一个连续数的中位数，来一个可以随机取出中位数 package com.bingoabin.algorithm.math; import java.

爱被打了一巴掌/ 2022年09月09日 00:28/ 0 赞/ 146 阅读

相关动态求解中位数

题意是这样的，给你一个序列寻找中位数？其实这个可以转化为TopK问题，但是假如这个数组不断的变化呢？这个时候可以考虑使用堆来解决。这是一个很经典的问题，值得反思和学习。

绝地灬酷狼/ 2022年05月26日 11:50/ 0 赞/ 159 阅读

相关动态规划求解‘货币兑付问题’

问题描述：在面值为(v1, v2, …, vn)n种货币中，需要支付y值的货款，应如何支付才能使货币支付的张数最少。设计动态规划算法求解该问题求解思路

小灰灰/ 2022年05月22日 11:50/ 0 赞/ 188 阅读

相关 Unique Paths（动态规划求解）

题目题目来源：[LeetCode][] 1. A robot is located at the top-left corner of a m x n grid (

Myth丶恋晨/ 2022年05月08日 02:42/ 0 赞/ 184 阅读

相关动态规划求解TSP圈

求解思路：动态规划的方法的最大难点就在于初始变量的确定，选择合适的初始变量才能更好的运用动态规划的方式解决问题。我在这里定义的变量就是d(i,S),

痛定思痛。/ 2022年04月25日 09:30/ 0 赞/ 235 阅读

相关中位数

include <iostream> using namespace std; int findpivot(int a[],int i,int j,in

本是古典何须时尚/ 2022年02月27日 12:36/ 0 赞/ 249 阅读

相关求中位数

输入两个未知长度的从小到大排列的数组，求出其中位数：思路: 1.首先将两组数据按照从小到大排列，拿他们的首元素进行对比，总是选取最小的放在新数组中，直到有一个数组遍历完

迷南。/ 2021年12月10日 08:41/ 0 赞/ 296 阅读

相关 P1168 中位数（动态中位数）

【题目描述】：输入N个32位有符号整数，当已输入的个数为奇数个时，输出此时的中位数。【输入描述】：第一行一个整数N；第二行N个32位有符号整数。【

我就是我/ 2021年11月26日 07:31/ 0 赞/ 306 阅读