学习
实践
活动
专区
工具
TVP
写文章

寻找中位数

2.返回数据的中位数: double findMedian(),返回其维护的数据的中位数中位数定义: 1.若数据个数为奇数,中位数是该组数排序后中间的数。 [1,2,3] -> 2 2.若数据个数为偶数,中位数是该组数排序后中间的两个数字的平均值。 double findMedian(){//返回该数据结构中维护的数据 } }; 思考与分析 如何获取中位数? 存储结构使用数组,每次添加元素或查找中位数时对数组排序, 再计算结果 时间复杂度 1.若添加元素时排序,addNum复杂度O(n),findMedian复杂度O(1) 2.若查询中位数时排序,addNum 获取中位数 ? 情况1:最大堆与最小堆元素个数相同时: ? 情况2:最大堆比最小堆多一个元素 ? 情况3:最大堆比最小堆少一个元素: ?

61930
  • 广告
    关闭

    新年·上云精选

    热卖云产品新年特惠,2核2G轻量应用服务器9元/月起,更多上云必备产品助力您轻松上云

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    Day7-线性表-堆-寻找中位数

    (),返回其维护的中位数 中位数定义: 若数据个数为奇数,中位数是该数据排序后中间的数。 【1,2,3】,return 2 若数据个数为偶数,中位数是该数据排序后中间两个数的平均值。 【1,2,3,4】,return 2.5 三 想想呗 ? 此时你脱口而出,这还不简单? 找个数组存啊,插入一个就排序啊,排完序之后,根据数组个数找中位数呗,这种题也拿来面我,渣渣 ? 此时的面试官狡黠一笑,哦,看起来可以,那你能不能给我一个时间复杂度为N的算法? 你: ? ,根据最大堆,最小堆元素个数来判断,是取谁的堆顶元素 这样我就做到了,时间复杂度为N,即,插完,同时排完,同时取中位数为O(1) 听起来有点拗口? 求中位数时,逻辑简单,注释中就写的非常清晰了 ? 需要注意的是,第二三种情况下,有逻辑,栗子中没覆盖到,大家还是动动手,体会一下为什么这样做 ?

    23810

    《三战Leetcode》寻找有序数组的中位数

    本篇文章大纲: 二、 题目   名称:寻找两个正序数组的中位数   题意:给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。 请你找出并返回这两个正序数组的中位数 。 它分为两种情况,一是当数组长度为奇数时,正中间的数为中位数,二是当数组长度为偶数时,通常是将最中间的两个数相加取平均值作 为中位数,具体看下图: 解法一:暴力破解   相信很多小伙伴一看到题目,脑海中就已经有了这种解题的思路 题目最终结果是要求中位数中位数又分为奇偶情况,那我们就可以将抽象求中位数成求有序数组中的第k小数,其中k就是对应的中位数(即 (m + n) /2,或者(m+n)/2 +1),这样我们就可以对k进行二分查找法找到符合条件的数值 通过上面的思路整理,我们可以看出此处使用了递归的思想,递归的出口则是当某个数组长度为了0时(此时中位数就是可以取不为0的数组中的值即可)或者是k=1(即求第1个小数,此时中位数则取两个数组中起始下标对应值最小的元素

    6910

    LeetCode【4】-- 寻找两个正序数组的中位数

    请你找出并返回这两个正序数组的中位数。 进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗? 示例 1: 输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2 示例 2: 输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5 示例 3: 输入:nums1 = [0,0], nums2 = [0,0] 思路以及解答 思路一:数组是有序的,利用双指针分别指向数组的第一个元素,对比大小,分别往后移动,合并到新的数组,然后直接取出中位数。 假设数组长度分别为n和m,求两次中位数再求和!!!啥意思,也就是由于有可能中位数是中间那两个数相加之后取平均,也可能是中间那个数。

    12130

    leetcode-寻找两个正序数组的中位数

    寻找两个正序数组的中位数 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/ 给定两个大小为 m 和 n 的正序(从小到大)数组 请你找出并返回这两个正序数组的中位数。 进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗? 示例 1: 输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2 示例 2: 输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5 示例 3: 输入:nums1 = [0,0], nums2 = [0,0] 代码有点长,思路很简单; 思路: 1、如果nums1为空,那么只需要查找第二个数组的中位数 2、如果nums2为空,那么只需要查找第一个数组的中位数 3、如果都不为空,就合并nums1和nums2,然后对合并后的数组做查找中位数的操作

    21421

    寻找两个正序数组的中位数LeetCode-4】

    Leetcode-4 寻找两个正序数组的中位数 原题链接 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/ func findMedianSortedArrays 奇数2n+1个,我们要取第n+1小的数 偶数2n个,我们要取第n和n+1小的数 在Go语言中,因为是强类型的,切片nums1与nums2是整数,返回值则是浮点数 这是我们遇到的第一道hard级别的题目, 基本解法 常规思路1 - 逐个寻找 常规思路来看,我们就是找第X小的数,那我们就一个一个找: func findMedianSortedArrays(nums1 []int, nums2 []int) } return float64(intSlice[len(intSlice) / 2 - 1] + intSlice[len(intSlice) / 2 ]) / 2 } 我个人觉得Go语言里的排序函数 这道题的问题是取中位数,但由于数组长度的奇偶性问题,这个中位数很难递归。所以,我们需要将问题做一个转化,实现找到第K小的数字,也就是下面的findKthSortedArrays函数。

    10310

    关注

    腾讯云开发者公众号
    10元无门槛代金券
    洞察腾讯核心技术
    剖析业界实践案例
    腾讯云开发者公众号二维码

    相关产品

    • 自然语言处理

      自然语言处理

      腾讯云自然语言处理(NLP)深度整合了腾讯内部顶级的 NLP 技术,依托千亿级中文语料累积,提供16项智能文本处理能力,包括智能分词、实体识别、文本纠错、情感分析、文本分类、词向量、关键词提取、自动摘要、智能闲聊、百科知识图谱查询等,满足各行各业的文本智能需求。

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券