精华内容
下载资源
问答
  • 中位数

    千次阅读 2015-10-11 18:07:50
    问题描述 中位数定义:一组数据按从小到大的顺序依次排列,处在中间位置的一个数或最中间两个数据的平均值...给出一组无序整数,中位数,如果最中间两个数的平均数,向下取整即可(不需要使用浮点数) 中位数

    问题描述
    中位数定义:一组数据按从小到大的顺序依次排列,处在中间位置的一个数或最中间两个数据的平均值(如果这组数的个数为奇数,则中位数为位于中间位置的那个数;如果这组数的个数为偶数,则中位数是位于中间位置的两个数的平均值).
    给出一组无序整数,求出中位数,如果求最中间两个数的平均数,向下取整即可(不需要使用浮点数)
    输入
    该程序包含多组测试数据,每一组测试数据的第一行为N,代表该组测试数据包含的数据个数,1 <= N <= 15000.
    接着N行为N个数据的输入,N=0时结束输入
    输出
    输出中位数,每一组测试数据输出一行
    输入示例

    4
    10
    30
    20
    40
    3
    40
    30
    50
    4
    1
    2
    3
    4
    0

    输出示例

    25
    40
    2

    提示
    这是也一道经典的算法问题,在企业面试里出现概率很高,是“找到第K大的数”的变种。先排序再找中位数自然是很直接的做法,但排序本身很慢。我们只想找到第n/2大的数,对于其他数的顺序我们并不关心。那么怎么在不排序的前提下找到第n/2大的数呢?
    源码

    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    {
        int numGroup = 0;
        vector<int> numAve;
        while(1)
        {
            int N = 0;
            cin >> N;       
            if (N == 0)
            {
                break;
            }
            else
            {           
                vector<int> sample(N);
                for (int i = 0; i < N; i++)
                {
                    cin >> sample[i];
                }
                if (N%2 != 0)
                {
                    int k = N/2 +1;
                    for (int i = 0; i < k; i++)
                    {
                        for (int j = i; j < N; j++)
                        {
                            if (sample[j] > sample[i])
                            {
                                int temp = sample[j];
                                sample[j] = sample[i];
                                sample[i] = temp;
                            }
                        }
                    }
                    numAve.push_back(sample[k-1]);
    //              cout << sample[k-1] << endl;
                } 
                else
                {
                    int k = N/2 +1;
                    for (int i = 0; i < k; i++)
                    {
                        for (int j = i; j < N; j++)
                        {
                            if (sample[j] > sample[i])
                            {
                                int temp = sample[j];
                                sample[j] = sample[i];
                                sample[i] = temp;
                            }
                        }
                    }
                    numAve.push_back((sample[k-2]+sample[k-1])/2);
    //              cout << (sample[k-2]+sample[k-1])/2 << endl;
                }
            }
            numGroup++;
        }
        for (int i = 0; i < numGroup; i++)
        {
            cout << numAve[i] << endl;
        }
        return 0;
    }

    ————————————————-2016/6/4———————————————–
    昨天师兄说起去面试的时候,他们让写个中值滤波的程序,想起找中位数这个问题。
    网上搜了一下,有些是借用了快排的思想做,最快的可达到最坏复杂度O(n)。
    有空要再好好看一下。

    展开全文
  • python:list的中位数

    千次阅读 2016-08-09 23:40:13
    L.sort() n = len(L) m = n/2 if n == 0: print 'None' elif n%2 == 0: print "%.1f"%((L[m]+L[m-1])/2.0) ...给你一个list L, 如 L=[0,1,2,3,4], 输出L的中位数(若结果为小数,则保留一位小数)。
    L.sort()
    n = len(L)
    m = n/2
    if n == 0:
        print 'None'
    elif n%2 == 0:
        print "%.1f"%((L[m]+L[m-1])/2.0)
    else:
        print L[m]

    原题目:

    给你一个list L, 如 L=[0,1,2,3,4], 输出L的中位数(若结果为小数,则保留一位小数)。
    



    下面内容转载自:http://www.linuxidc.com/Linux/2014-11/108912.htm,来源:Linux社区 作者:tanzhangwen,如侵权请联系删除,抱歉。


    sorted与sort的区别

    1. sorted函数是内建函数,而sort是序列的内部函数,所以它们调用方式不一样,另外sorted函数多了一个系列迭代器参数

    2. sorted函数不改变参数系列,但是返回排好序的序列副本;而sort作为序列的内部函数,调用完后会对调用的序列进行排序


    下面的结果很好的说明了这些:

    >>> list=[2,1]
    >>> x=sorted(list)
    >>> x
    [1, 2]
    >>> list
    [2, 1]
    >>> y=list.sort()
    >>> y
    >>> list
    [1, 2]

    sorted与sort的参数:

    sorted与sort除了一个是序列作为参数,一个是序列调用该函数,其他参数几乎完全一致,下面逐一来介绍其用法及效果:

    1. 默认用法

    由于sort函数的参数reverse,key,cmp都提供了缺省参数,所以我们可以直接不指定这些参数值调用该函数。但是它必须有一个前提,就是list中存放的类型是可比较的。否则就会弹出错误“Type Error: unorderable type"。

    2. reverse参数

    当取值为True时候就是倒序排,默认为False正序从小到大排

    >>> list.sort(reverse=False)
    >>> list
    [1, 2]
    >>> list.sort(reverse=True)
    >>> list
    [2, 1]

    3. key参数

    key表示用来做比较的值,这个主要对自定义的数据类型有用。下面用一个例子来诠释:

    # Definition for an interval.
    class Interval:
     def __init__(self, s=0, e=0):
      self.start = s
      self.end = e

    # Initialize the Interval list
    list = []
    for i in range(10,7,-1):
     for j in range(11,i,-1):
      list.append(Interval(i,j))

    这里我们定义了Interval为[s,e]的数据结构并且初始化了。对于这个问题,显然我们用缺省的参数来调用会出错,因为我们没有提供可比较的函数来比较类型Interval。对于这样的情况,我们就可以指定比较的key来解决。

    #Sort the Interval list
    list2 = sorted(list,key=lambda x:x.start)

    #Output the Interval list
    for x in list:
     print("[%d,%d]"%(x.start,x.end))
    for x in list2:
     print("[%d,%d]"%(x.start,x.end))

    这里我们基于Interval.start作为key进行排序了。

    可是接着问题来了,如果我不仅比较Interval.start,当Interval.start相等时候,还想比较Interval.end,该怎么办?

    #Sort the Interval list based on Interval.start and Interval.end
    list2 = sorted(list,key=lambda x:(x.start,x.end))

    我们用元祖(Interval.start,Interval.end)作为key来比较,而元祖有默认的cmp函数。这就达到了目标。

    4. cmp参数

    我们可以通过自定义函数或则使用简洁的lambda来作为参数传给cmp

    #Sort the Interval list based on Interval.start and Interval.end
    def cmpInterval(a, b):
     if a.start != b.start:
      return cmp(a.start,b.start)
     return cmp(a.end,b.end)
    list1 = sorted(list,cmp = cmpInterval)
    list2 = sorted(list,cmp = lambda x,y:cmp(x.start,y.start))

    不过比较遗憾的是发现在python 3.x中传入cmp函数会出现一个错误:TypeError: 'cmp' is an invalid keyword argument for this function
    这时候我们就需要使用key来绕过这个问题。另外一个建议就是我们尽量使用key而不是cmp来排序以提高运行速度。
    展开全文
  • 求多个有序数组的中位数

    万次阅读 2012-09-15 10:57:47
    题目:求解多个有序数组的中位数 题目的意思是如果多个有序数组...该题目可能有很多种实现方法,而我们给出一种仅依赖中位数性质的算法。如果存在一个已经排好序的大数组(有序数列),则会发现几个性质: 对

    题目:求解多个有序数组的中位数


    题目的意思是如果多个有序数组能在一起排序,则取位置为中间的数字,如果有奇数个数字则中位数只有一个;若为偶数个则有两个,一般取第一个,也称下中位。但不能把数组合在一起做插入或快速排序,因为数据可能是海量的。


    该题目可能有很多种实现方法,而我们给出一种仅依赖中位数性质的算法。如果存在一个已经排好序的大数组(有序数列),则会发现几个性质:

    1. 对称性:中位数前面的数字与后面的数字一样多(在偶数元素情况下或相差1)
    2. 确定性:若某个数字前后的数字数量相同(或相差1)则为该数列的中位数
    3. 不变性:删除前N个元素与后N个元素后,中位数不变
    4. 关联性:从大数组中按顺序任意取走n-1组元素,与剩下的元素共构成n个子列,每个子列存在中位数:m1,m1...mn,min,max分别为其中最小者与最大者,则原数列的中位数m满足:min<=m<=max
      该性质可通过反证法获得
    根据上述性质构造下面基于3分查找的算法:
    1. 输入多个有序数组查找其中位数m
    2. 计算个数组的中位数,并计算其最小者min与最大者max,则m必满足min<=m<=max
    3. 计算min之前所有的数字lTripCount(在所有数组)及max之后所有的数字rTripCount,如果二者相同,则min与max都为中位数,递归结束
    4. 计算所有数组中属于区间[min,max]的中位数(小于min或大于max的全被舍弃)m1,如果m1满足lTripCount==rTripCount,则为中位数,递归结束
    5. 如果lTripCount<rTripCount,则中位数m一定属于区间[min,m1]
    6. 如果lTripCount>rTripCount,则中位数m一定属于区间(m1,max]
    7. 递归上述过程
    8. 若某个递归后发现各数组剩余的数据小于某个阀值,则考虑一起计算,从而终止递归
    该算法的主要思想是利用子数组的中位数逼近全数组的中位数,具体过程如下: 
    要排序的全数组:

    其中10便是要求解的中位数,数组A被划分为下面三个子数组:

    计算步骤:
    1. 分别计算A1,A2,A3的中位数,分别为7,9,11
    2. 根据关联性,则要寻找的中位数(10)必定满足7<=m<=11
    3. 从A1,A2,A3中去除小于7,大于11的数,此时各子数组的数据情况如下:

    4. 继续计算各子数组的中位数,可的A1:10,A2:9,A3:11,因为此时各数组只剩一个元素,故根据假设可在一起计算其中位数10
    5. 以10为中心计算lTripCount、rTripCount,经过计算二者相同,根据确定性可断定10为最终的中位数;如果lTreipCount与rTripCount不同,则可推导中位数会落在哪个区间(参考上面的算法描述),从而递归上面的过程
    因为每次都根据最小中位数与最大中位数过滤,故每次计算可大约砍掉2/3的数据,算法大约以3n的速度收敛。
    上述算法可能会产生一个无法收敛的特殊场景:如果某个计算过程出现最小中位数为当前有效数据的最小值,而最大中位数为最大值,则无法过滤掉更多的数据,解决该问题的办法是根据不变性,同时删除最小中位数与最大中位数。

    展开全文
  • 堆排序:动态数组求中位数

    千次阅读 2016-04-10 00:43:34
    题目描述输入一组整数a1, a2, …, an ,每输入一个整数,输出到此时为止的中位数中位数定义:如果数串的大小是偶数 2j,中位数是从小到大排列的第 j 个数;如果数串的大小是奇数 2j+1,中位数是从小到大排列的第 ...

    题目描述

    输入一组整数a1, a2, …, an ,每输入一个整数,输出到此时为止的中位数。
    中位数定义:如果数串的大小是偶数 2j,中位数是从小到大排列的第 j 个数;如果数串的大小是奇数 2j+1,中位数是从小到大排列的第 j+1 个数。 
    

    输入

    一组整数,数字和数字之间以空格隔开。
    (在实际控制台编程的时候,输入数组之后输入回车,还需输入一个终止符Ctr+Z)
    

    输出

    一组整数,数字和数字之间以空格隔开。最后一个数后面也有空格。 
    第 i 个输出的整数,是前 i 个输入的中位数。
    

    样例输入

    -18 -2 14 -20 -6 7 2 14 11 6 
    

    样例输出

    -18 -18 -2 -18 -6 -6 -2 -2 2 2 
    

    提示

    时间复杂度请不要超过O(nlogn)。
    由于输入输出的量会比较大,因此推荐使用c语言中的scanf和printf函数来进行输入输出,能比c++中cin和cout节省许多时间。
    

    解决方法

    很容易想到的方法是先排序,再找中位数。每输入一个数字,对已输入的数字进行插入排序。输入第k个数字,由于之前的数字已经排好了,所以用二分插入排序有O(logk) <= O(logn)的比较次数。这样总的比较次数也有O(n*logn)。但是这个方法有一个问题,就是移动元素的次数可能很多(最坏情况,每次新来的元素都是最小的,这样要移动O(n^2)次)。

    利用堆排序可能很好的解决这个问题(这里假设大家知道如何在堆中进行插入和删除)。我们维护两个数组和一个变量mid_value。两个数组分别是小于mid_value的元素组成的的大顶堆(即堆顶是最大的元素)和大于mid_value的元素组成的小顶堆。如果新来的数字比mid_value大,则将其插入大于mid_value的最小堆。否则,插入最大堆。
    case<1> 如果此时大于mid_value的元素比小于mid_value的多两个,那么将mid_value插入小于mid_value的最大堆,将大于mid_value的最小堆的最小值赋给mid_value,并且删除该最小堆的堆顶。
    case<2> 如果此时小于mid_value的元素比大于mid_value的元素多。那么将mid_value插入大于mid_value的小顶堆中,将小于mid_value的大顶堆堆顶赋给mid_value,并且删除该堆顶。

    插入第k个元素,堆的插入和删除操作的复杂度(不管是比较次数还是移动次数)都是O(logk)<=O(logn),这样总的时间复杂度就是O(n*logn)。

    展开全文
  • bfptr算法(即中位数中位数算法)

    万次阅读 多人点赞 2018-08-25 22:35:16
    BFPRT算法是解决从n个数中选择第k大或第k小的这个经典问题的著名算法,但很多人并不了解其细节。本文将首先介绍求解这个第k小数字问题的几个思路,然后重点介绍在最坏情况下复杂度仍然为O(n)的BFPRT算法。 一 ...
  • python求解中位数、均值、众数

    万次阅读 2019-02-16 11:19:19
    一、求中位数  中位数(又称中值,英语:Median),统计学中的专有名词,代表一个样本、种群或概率分布中的一个数值,其可将数值集合划分为相等的上下两部分。对于有限的数集,可以通过把所有观察值高低排序后找出...
  • 一个无序数组的中位数

    千次阅读 2017-08-03 17:33:07
    一个无序数组的中位数 中位数是将数组排序之后,数组个数为奇数时,取中间的即为中位数;数组个数为偶数时,取中间两个的平均值即为中位数。 思路一: 要取得中位数,即给数组排序,使用任意排序算法均可,然后按...
  • python的列表List均值和中位数实例

    千次阅读 2020-03-08 21:59:41
    这篇文章主要介绍了python的列表List均值和中位数实例,具有好对参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 我就废话不说了,直接上代码吧! import numpy as np a = [2,4,6,8,10] average_a = np...
  • 一组数据中如果有特别大的数或特别小的数时,一般用中位数 一组数据比较(20个以上),范围比较集中,一般用众数 其余情况一般还是平均数比较精确 一、联系与区别:  1、平均数是通过计算得到的,因此它会因...
  • step1:出数组的中位数的值O(n) step2:计算数组每个数与中位数差的绝对值,存于另一个数组B中O(n) step3:出数组B中第k小的数ret O(n) step4:计算数组S中与ret差的绝对值小于ret的数并输出O(n) 其中,step...
  • Python计算中位数 numpy.median

    万次阅读 多人点赞 2017-07-04 17:46:48
    计算沿指定轴的中位数 返回数组元素的中位数其函数接口为:median(a, axis=None, out=None, overwrite_input=False, keepdims=False)其中各参数为: a:输入的数组; axis:计算哪个轴上的中位数,比如...
  • 两个有序数组的中位数

    千次阅读 2011-08-14 11:28:43
    两个有序数组的中位数   如果有两个有序的数组,都是已经排好序的。那么它们的中位数应该怎样呢。如果采用对这两个数组进行排序的方法,最快的时间复杂度也要o(nlogn)的时间。但是,如果采用中位数和顺序统...
  • 自定类型元素序列的中位数 PAT

    千次阅读 2016-02-28 12:41:54
    PAT基础编程题目集中的自定类型元素序列的中位数,通过率低,只有6%,题目简单,原题如下所述: 本题要求实现一个函数,N个集合元素A[]的中位数,即序列中第\lceil N/2 \rceil⌈N/2⌉大的元素。...
  • java实现二十一水仙花(21水仙花

    万次阅读 多人点赞 2019-07-30 12:24:03
    一个N的十进制正整数,如果它的每个上的数字的N次方的和等于这个本身,则称其为花朵。 例如: N=3时,153就满足条件,因为 1^3 + 5^3 + 3^3 = 153,这样的数字也被称为水仙花(其中,“”表示乘方,53...
  • 问题描述问题简单,就是在两个有序的整数数组里(数组A长度为m, 数组B长度为n),找到两个数组合并后的中位数中位数中位数就是在一个有序数组中,位于中间的数字,假如数组元素个数为偶数,则取两个中间数字的...
  • 我深入研究时,我意识到我难理解为给定的数据选择哪个集中趋势指标有三种:平均值,中位数和众数。 所以我决定写这篇文章来帮助像我一样在这个领域里的新人来弄明白这一点,而不是害怕数据和统计。这里我们使用...
  • 转:... 题目介绍: 输入为不断地数字流,实时显示出当前已经输入的数字序列的中位数 解答: 求中位数的方法很多,对于大数据量最经典是桶的计数方法,但是对于这个问题不适用,因为数据
  • Spark如何求解中位数

    万次阅读 2020-05-29 14:36:02
    关于求解中位数,我们知道在Python中直接有中位数处理函数(mean),比如在Python中求解一个中位数,代码简单。 Python计算中位数 import numpy as np nums = [1.1,2.2,3.3,4.4,5.5,6.6] 均值 np.mean(nums) ...
  • 寻找两个正序数组的中位数1、问题分析2、问题解决3、总结 1、问题分析 题目链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/ 具体思路是: 1、 根据两个数组的总长度计算是否是 ...
  •  中位数:分类数据组的中间值(如果数据个数为偶数,则是两个中间数值和的一半)  众数:数据组中出现次数最多的值(或者一组值)   异常值:比几乎其他所有数字都要 大/小 很多的数值   加权平均值:对变量在...
  • 给一个无序数组array和数组长度n,找出其中的中位数(这里考虑n为奇数) Sample: ***** Input: ***** @[@(500),@(120),@(7),@(220),@(3),@(8),@(4),@(200),@(100) ***** Output: ***** 100 解法一:将数组...
  • 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。 你可以假设 nums1 和 nums2 不同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0 示例 2: nums1 = [1, 2] nums...
  • 从数据流中获取中位数

    万次阅读 2020-02-29 11:55:55
    从数据流中获取中位数需求描述需求分析C++代码如下python代码 需求描述   有一个动态的数据流,如何比较快的获得数据流的中位数。这个过程中,数据流可能会有新的数据加入。中位数定义为元素个数为奇数的序列的...
  • MySQL查询一组数据的众数和中位数

    千次阅读 2019-03-05 14:00:41
    查询一组数据的众数: 方法1:仅适用于一组数据只有一个众数的情况 1)首先对数据按照值的不同进行分组,并对每组的数据进行计数,再根据计数的大小进行降序排序;... 2)使用max函数找出统计个的...
  • 两个有序序列的中位数。(要求时间复杂度为O(logN)) 2. 问题描述 已知有两个等长的非降序序列S1, S2, 设计函数S1与S2并集的中位数。有序序列A0, A1…AN-1的中位数指A(N-1)/2的值,即第[(N+1)/2]个数(A0为...
  • Stata:个变量组间均值\中位数差异检验

    万次阅读 多人点赞 2019-05-30 10:34:28
      作者:韩少真(西北大学) || 刘婉青(西北大学) Stata 连享会: 知乎 | 简书 | 码云 | CSDN ...2019暑期Stata现场班,7.17-26日,北京,连玉君+刘瑞明 主讲 ... Stata实现组间均值或中位数差异检验的常见...
  • 找出序列中的中位数

    千次阅读 2015-09-05 22:47:48
    序列中的中位数
  • 【分步详解】两个有序数组中的中位数和Top K问题

    万次阅读 多人点赞 2016-04-09 21:50:00
    这也是一道leetcode的经典题目:《LeetCode》解题笔记:004. Median of Two Sorted Arrays[H] 问题介绍 预备知识 先解释下割 ...代码问题介绍这个问题大致是说,如何在给定的两个有序数组里面找其中的
  • 寻找两个有序数组的中位数

    万次阅读 2020-03-12 15:22:22
      之前讲解过一道数据流求中位数的题目,但是仔细一想觉得那一次对几种数据结构简单的分析了一下实现,并没有对中位数的题目做一个凝练总结,这一次借这个机会,好好整理一下思路。 题目描述   给定两个大小为 m...
  • python作为数据分析的利器,极差、平均数、中位数、众数与方差是常用的,然而,在python进行统计往往要使用外部的python库numpy,这个库不难装,然而,如果单纯只是极差、平均数、中位数、众数与方差,还是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,124,556
精华内容 449,822
关键字:

当数很多的时候怎么求中位数