精华内容
下载资源
问答
  • bfptr算法(即中位数中位数算法)

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

    BFPRT算法是解决从n个数中选择第k大或第k小的数这个经典问题的著名算法,但很多人并不了解其细节。本文将首先介绍求解这个第k小数字问题的几个思路,然后重点介绍在最坏情况下复杂度仍然为O(n)的BFPRT算法。

    一 基本思路

    关于选择第k小的数字有许多方法,其效率和复杂度各不一样,可以根据实际情况进行选择。

    1. 将n个数排序(比如快速排序或归并排序),选取排序后的第k个数,时间复杂度为O(nlogn)。使用STL函数sort可以大大减少编码量。
    2. 将方法1中的排序方法改为线性时间排序算法(如基数排序或计数排序),时间复杂度为O(n)。但线性时间排序算法使用限制较多,不常使用。
    3. 维护一个k个元素的最大堆,存储当前遇到的最小的k个数,时间复杂度为O(nlogk)。这种方法同样适用于海量数据的处理。
    4. 部分的选择排序,即把最小的放在第1位,第二小的放在第2位,直到第k位为止,时间复杂度为O(kn)。实现非常简单。
    5. 部分的快速排序(快速选择算法),每次划分之后判断第k个数在左右哪个部分,然后递归对应的部分,平均时间复杂度为O(n)。但最坏情况下复杂度为O(n^2)。
    6. BFPRT算法,修改快速选择算法的主元选取规则,使用中位数的中位数作为主元,最坏情况下时间复杂度为O(n)

    二 快速选择算法

    快速选择算法就是修改之后的快速排序算法,前面快速排序的实现与应用这篇文章中讲了它的原理和实现。

    其主要思想就是在快速排序中得到划分结果之后,判断要求的第k个数是在划分结果的左边还是右边,然后只处理对应的那一部分,从而达到降低复杂度的效果。

    在快速排序中,平均情况下数组被划分成相等的两部分,则时间复杂度为T(n)=2*T(n/2)+O(n),可以解得T(n)=nlogn。
    在快速选择中,平均情况下数组也是分成相等的两部分,但是只处理其中一部分,于是T(n)=T(n/2)+O(n),可以解得T(n)=O(n)。

    但是两者在最坏情况下的时间复杂度均为O(n^2),出现在每次划分之后左右总有一边为空的情况下。为了避免这个问题,需要谨慎地选取划分的主元,一般的方法有:

    1. 固定选择首元素或尾元素作为主元。
    2. 随机选择一个元素作为主元。
    3. 三数取中,选择三个数的中位数作为主元。一般是首尾数,再加中间的一个数或者随机的一个数。

    ============================================================

    通常,我们需要在一大堆数中求前K大的数,或者求前K小的。比如在搜索引擎中求当天用户点击次数排名前10000的热词;在文本特征选择中求IF-IDF值按从大到小排名前K个的等等问题,都涉及到一个核心问题,即TOP-K问题

    通常来说,TOP-K问题可以先对所有数进行快速排序,然后取前K大的即可。但是这样做有两个问题。

    (1)快速排序的平均复杂度为,但最坏时间复杂度为,不能始终保证较好的复杂度。

    (2)我们只需要前K大的,而对其余不需要的数也进行了排序,浪费了大量排序时间。

    除这种方法之外,堆排序也是一个比较好的选择,可以维护一个大小为K的堆,时间复杂度为

    我们的目的是求前K大的或者前K小的元素,实际上有一个比较好的算法,叫做BFPTR算法,又称为中位数的中位数算法,它的最坏时间复杂度为,它是由Blum、Floyd、Pratt、Tarjan、Rivest 提出。

    该算法的思想是修改快速选择算法的主元选取方法,提高算法在最坏情况下的时间复杂度。我们先来看看快速排序是如何进行的。

    一趟快速排序的过程如下

    (1)先从序列中选取一个数作为基准数。

    (2)将比这个数大的数全部放到它的右边,把小于或者等于它的数全部放到它的左边。

    一趟快速排序也叫做Partion,即将序列划分为两部分,一部分比基准数小,另一部分比基准数大,然后再进行分治过程,因为每一次Partion不一定都能保证划分得很均匀,所以最坏情况下的时间复杂度不能保证总是为

    对于Partion过程,通常有两种方法:

    (1)两个指针从首尾向中间扫描(双向扫描)

     这种方法可以用挖坑填数来形容,比如

     

        

     

        初始化:i = 0; j = 9; pivot = a[0];

        现在a[0]保存到了变量pivot中了,相当于在数组a[0]处挖了个坑,那么可以将其它的数填到这里来。从j开始向前找一个小于或者等于pivot的数,即将a[8]填入a[0],但a[8]又形成了一个新坑,再从i开始向后找一个大于pivot的数,即a[3]填入a[8],那么a[3]又形成了一个新坑......

        就这样,直到i==j才停止,最终得到结果如下

     

        

     

        上述过程就是一趟快速排序

     

    代码:

    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    #include <algorithm>
    #include <time.h>
    
    using namespace std;
    const int N = 10005;
    
    int Partion(int a[], int l, int r)
    {
    	int i = l;
    	int j = r;
    	int pivot = a[l];
    	while (i < j)
    	{
    		while (a[j] >= pivot && i < j)
    			j--;
    		a[i] = a[j];
    		while (a[i] <= pivot && i < j)
    			i++;
    		a[j] = a[i];
    	}
    	a[i] = pivot;
    	return i;
    }
    
    void QuickSort(int a[], int l, int r)
    {
    	if (l < r)
    	{
    		int k = Partion(a, l, r);
    		QuickSort(a, l, k - 1);
    		QuickSort(a, k + 1, r);
    	}
    }
    
    int a[N];
    
    int main()
    {
    	int n;
    	while (cin >> n)
    	{
    		for (int i = 0; i < n; i++)
    			cin >> a[i];
    		QuickSort(a, 0, n - 1);
    		for (int i = 0; i < n; i++)
    			cout << a[i] << " ";
    		cout << endl;
    	}
    	return 0;
    }

    (2)两个指针一前一后逐步向前扫描(单向扫描)

    代码:

    #include <iostream>  
    #include <string.h>  
    #include <stdio.h>  
       
    using namespace std;  
    const int N = 10005;  
       
    int Partion(int a[], int l, int r)  
    {  
        int i = l - 1;  
        int pivot = a[r];  
        for(int j = l; j < r; j++)  
        {  
            if(a[j] <= pivot)  
            {  
                i++;  
                swap(a[i], a[j]);  
            }  
        }  
        swap(a[i + 1], a[r]);  
        return i + 1;  
    }  
       
    void QuickSort(int a[], int l, int r)  
    {  
        if(l < r)  
        {  
            int k = Partion(a, l, r);  
            QuickSort(a, l, k - 1);  
            QuickSort(a, k + 1, r);  
        }  
    }  
       
    int a[N];  
       
    int main()  
    {  
        int n;  
        while(cin >> n)  
        {  
            for(int i = 0; i < n; i++)  
                cin >> a[i];  
            QuickSort(a, 0, n - 1);  
            for(int i = 0; i < n; i++)  
                cout << a[i] << " ";  
            cout << endl;  
        }  
        return 0;  
    }  

    实际上基于双向扫描的快速排序要比基于单向扫描的快速排序算法快很多。接下来,我们学习BFPTR算法的原理。

    BFPTR算法中,仅仅是改变了快速排序Partion中的pivot值的选取,在快速排序中,我们始终选择第一个元素或者最后一个元素作为pivot,而在BFPTR算法中,每次选择五分中位数的中位数作为pivot,这样做的目的就是使得划分比较合理,从而避免了最坏情况的发生。算法步骤如下:

    (1)将输入数组的个元素划分为组,每组5个元素,且至多只有一个组由剩下的个元素组成。

    (2)寻找个组中每一个组的中位数,首先对每组的元素进行插入排序,然后从排序过的序列中选出中位数。

    (3)对于(2)中找出的个中位数,递归进行步骤(1)和(2),直到只剩下一个数即为这个元素的中位数,找到中位数后并找到对应的下标

    (4)进行Partion划分过程,Partion划分中的pivot元素下标为

    (5)进行高低区判断即可。

    本算法的最坏时间复杂度为,值得注意的是通过BFPTR算法将数组按第K小(大)的元素划分为两部分,而这高低两部分不一定是有序的,通常我们也不需要求出顺序,而只需要求出前K大的或者前K小的。

    另外注意一点,求第K大就是求第n-K+1小,这两者等价。TOP K问题在工程中有重要应用,所以很有必要掌握。

    代码:

    #include <iostream>  
    #include <string.h>  
    #include <stdio.h>  
    #include <time.h>  
    #include <algorithm>  
       
    using namespace std;  
    const int N = 10005;  
       
    int a[N];  
       
    //插入排序  
    void InsertSort(int a[], int l, int r)  
    {  
        for(int i = l + 1; i <= r; i++)  
        {  
            if(a[i - 1] > a[i])  
            {  
                int t = a[i];  
                int j = i;  
                while(j > l && a[j - 1] > t)  
                {  
                    a[j] = a[j - 1];  
                    j--;  
                }  
                a[j] = t;  
            }  
        }  
    }  
       
    //寻找中位数的中位数  
    int FindMid(int a[], int l, int r)  
    {  
        if(l == r) return a[l];  
        int i = 0;  
        int n = 0;  
        for(i = l; i < r - 5; i += 5)  
        {  
            InsertSort(a, i, i + 4);  
            n = i - l;  
            swap(a[l + n / 5], a[i + 2]);  
        }  
       
        //处理剩余元素  
        int num = r - i + 1;  
        if(num > 0)  
        {  
            InsertSort(a, i, i + num - 1);  
            n = i - l;  
            swap(a[l + n / 5], a[i + num / 2]);  
        }  
        n /= 5;  
        if(n == l) return a[l];  
        return FindMid(a, l, l + n);  
    }  
       
    //寻找中位数的所在位置  
    int FindId(int a[], int l, int r, int num)  
    {  
        for(int i = l; i <= r; i++)  
            if(a[i] == num)  
                return i;  
        return -1;  
    }  
       
    //进行划分过程  
    int Partion(int a[], int l, int r, int p)  
    {  
        swap(a[p], a[l]);  
        int i = l;  
        int j = r;  
        int pivot = a[l];  
        while(i < j)  
        {  
            while(a[j] >= pivot && i < j)  
                j--;  
            a[i] = a[j];  
            while(a[i] <= pivot && i < j)  
                i++;  
            a[j] = a[i];  
        }  
        a[i] = pivot;  
        return i;  
    }  
       
    int BFPTR(int a[], int l, int r, int k)  
    {  
        int num = FindMid(a, l, r);    //寻找中位数的中位数  
        int p =  FindId(a, l, r, num); //找到中位数的中位数对应的id  
        int i = Partion(a, l, r, p);  
       
        int m = i - l + 1;  
        if(m == k) return a[i];  
        if(m > k)  return BFPTR(a, l, i - 1, k);  
        return BFPTR(a, i + 1, r, k - m);  
    }  
       
    int main()  
    {  
        int n, k;  
        scanf("%d", &n);  
        for(int i = 0; i < n; i++)  
            scanf("%d", &a[i]);  
        scanf("%d", &k);  
        printf("The %d th number is : %d\n", k, BFPTR(a, 0, n - 1, k));  
        for(int i = 0; i < n; i++)  
            printf("%d ", a[i]);  
        puts("");  
        return 0;  
    }  
       
    /** 
    10 
    72 6 57 88 60 42 83 73 48 85 
    5 
    */  

    关于本算法最坏时间复杂度为的证明可以参考《算法导论》9.3节,即112页,有详细分析。

     

    原文链接:https://blog.csdn.net/wyq_tc25/article/details/51801885

    展开全文
  • java 计算中位数方法

    万次阅读 2019-01-04 15:51:14
    最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个 先说说什么是中位数中位数就是中间的那个数, 如果一个集合是奇数个,那么中位数就是按大小排列...

    最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个

    先说说什么是中位数:

    中位数就是中间的那个数,

    如果一个集合是奇数个,那么中位数就是按大小排列后,最中间那个数,

    如果一个集合是偶数个,那么中位数就是按大小排列后,最中间那2个数的平均数。

    比如:

    1,2,3,4,5  那中位数就是3

    1,2,3,4,5,6 那中位数就是 (3+4)/2 = 3.5

    知道逻辑后方法就很简单了 下面是代码

    public static void main(String[] args) {
    	List<Integer> total = new ArrayList<Integer>();
    	total.add(4);
    	total.add(2);
    	total.add(3);
    	total.add(1);
    	total.add(5);
    	total.add(6);
    	double a = median(total);
    	System.out.println(a);
    }
    private static double median(List<Integer> total) {
    	double j = 0;
    	//集合排序
        Collections.sort(total);
        int size = total.size();
        if(size % 2 == 1){
        	j = total.get((size-1)/2);
        }else {
        	//加0.0是为了把int转成double类型,否则除以2会算错
        	j = (total.get(size/2-1) + total.get(size/2) + 0.0)/2;
        }
    	return j;
    }

    1. 方法内先判断集合是奇数还是偶数,如果是奇数那么就是第n+1/2个数 ,也就是下标为n-1/2的值,

    如果是偶数 就是第n/2和n/2+1的数的平均值 也就是下标为n/2-1和n/2的平均值

    2. 该方法传入的是list集合  如果为数组  可以先用Arrays.aslist()方法转换后传入

    展开全文
  • 一组数据中如果有特别大的数或特别小的数时,一般用中位数 一组数据比较多(20个以上),范围比较集中,一般用众数 其余情况一般还是平均数比较精确 一、联系与区别:  1、平均数是通过计算得到的,因此它会因...

    原文链接:http://www.360doc.com/content/18/0717/09/57858800_771067787.shtml

    个人理解,说简单点:
    一组数据中如果有特别大的数或特别小的数时,一般用中位数
    一组数据比较多(20个以上),范围比较集中,一般用众数
    其余情况一般还是平均数比较精确

    一、联系与区别:

      1、平均数是通过计算得到的,因此它会因每一个数据的变化而变化。

      2、中位数是通过排序得到的,它不受最大、最小两个极端数值的影响.中位数在一定程度上综合了平均数和中位数的优点,具有比较好的代表性。部分数据的变动对中位数没有影响,当一组数据中的个别数据变动较大时,常用它来描述这组数据的集中趋势。另外,因中位数在一组数据的数值排序中处中间的位置,

      3、众数也是数据的一种代表数,反映了一组数据的集中程度.日常生活中诸如“最佳”、“最受欢迎”、“最满意”等,都与众数有关系,它反映了一种最普遍的倾向.

    二、平均数、中位数和众数它们都有各自的的优缺点.

    平均数:
    (1)需要全组所有数据来计算;
    (2)易受数据中极端数值的影响.

    中位数:
    (1)仅需把数据按顺序排列后即可确定;
    (2)不易受数据中极端数值的影响.

    众数:
    (1)通过计数得到;
    (2)不易受数据中极端数值的影响

    关于“中位数、众数、平均数”这三个知识点的理解,我简单谈谈自己的认识和理解。
    ⒈众数。
    一组数据中出现次数最多的那个数据,叫做这组数据的众数。
    ⒉众数的特点。
    ①众数在一组数据中出现的次数最多;②众数反映了一组数据的集中趋势,当众数出现的次数越多,它就越能代表这组数据的整体状况,并且它能比较直观地了解到一组数据的大致情况。但是,当一组数据大小不同,差异又很大时,就很难判断众数的准确值了。此外,当一组数据的那个众数出现的次数不具明显优势时,用它来反映一组数据的典型水平是不大可靠的。
    3.众数与平均数的区别。
    众数表示一组数据中出现次数最多的那个数据;平均数是一组数据中表示平均每份的数量。
    4.中位数的概念。
    一组数据按大小顺序排列,位于最中间的一个数据(当有偶数个数据时,为最中间两个数据的平均数)叫做这组数据的中位数。
    5.众数、中位数及平均数的求法。
    ①众数由所给数据可直接求出;②求中位数时,首先要先排序(从小到大或从大到小),然后根据数据的个数,当数据为奇数个时,最中间的一个数就是中位数;当数据为偶数个时,最中间两个数的平均数就是中位数。③求平均数时,就用各数据的总和除以数据的个数,得数就是这组数据的平均数。
    6.中位数与众数的特点。
    ⑴中位数是一组数据中唯一的,可能是这组数据中的数据,也可能不是这组数据中的数据;
    ⑵求中位数时,先将数据有小到大顺序排列,若这组数据是奇数个,则中间的数据是中位数;若这组数据是偶数个时,则中间的两个数据的平均数是中位数;
    ⑶中位数的单位与数据的单位相同;
    ⑷众数考察的是一组数据中出现的频数;
    ⑸众数的大小只与这组数的个别数据有关,它一定是一组数据中的某个数据,其单位与数据的单位相同;
    (6)众数可能是一个或多个甚至没有;
    (7)平均数、众数和中位数都是描述一组数据集中趋势的量。
    7.平均数、中位数与众数的异同:
    ⑴平均数、众数和中位数都是描述一组数据集中趋势的量;
    ⑵平均数、众数和中位数都有单位;
    ⑶平均数反映一组数据的平均水平,与这组数据中的每个数都有关系,所以最为重要,应用最广;
    ⑷中位数不受个别偏大或偏小数据的影响;
    ⑸众数与各组数据出现的频数有关,不受个别数据的影响,有时是我们最为关心的数据。
    8.统计量。
    平均数、众数和中位数都叫统计量,它们在统计中,有着广泛的应用。
    9.举手表决法。
    在生活中,往往会有由多数人来从众多答案中选择一个的情形,一般都利用“举手表决”方式来解决问题。即在统计出所有提议及相应票数的情况下,看各票数的众数是否超过总票数的一半,如果众数超过了总票数的一半,选择的最终答案就是这个众数。如果出现了双众数(两个众数),可对这两个众数采用抓阄、抽签或投掷硬币等办法选出最终的答案。
    10.平均数、众数和中位数三种统计数据在生活中的意义。
    平均数说明的是整体的平均水平;众数说明的是生活中的多数情况;中位数说明的是生活中的中等水平。
    11.如何通过平均数、众数和中位数对表面现象到背景材料进行客观分析。
    在个别的数据过大或过小的情况下,“平均数”代表数据整体水平是有局限性的,也就是说个别极端数据是会对平均数产生较大的影响的,而对众数和中位数的影响则不那么明显。所以,这时要用众数活中位数来代表整体数据更合适。即:如果在一组相差较大的数据中,用中位数或众数作为表示这组数据特征的统计量往往更有意义。

    算数平均数、中位数与众数——统计量背后的故事

    现代经济社会的数字化程度越来越高,我们会发现在我们生活的这个世界里充斥着各种各样的数字。人们在描述事物或过程时,人们也已经习惯性的偏好于接受数字信息以及对于各种数字的整理和分析。因此,社会经济统计越发的重要。统计学一定是基于现实经济社会发展的需要牵引而不断发展的。在运用统计方法、观察统计数字时不能仅仅看到数字,更要看到数字背后的故事。其实统计学作为一门工具能够帮助我们更为深刻的理解抽象的社会经济现象。当我们仔细发掘其中涵义就会发现,其实自然科学与社会科学并不是相隔千里,它们有着很多地方可以相互的对应,存在普遍而深刻的联系。
    笔者曾在为一些本科学生讲授统计学而准备教案时,产生了一些似乎有些勉强,但的确可以训练思维的想法。下面以对于如何理解“算数平均数、中位数与众数”之间的关系为例说一说统计量背后的故事。这三个统计量都是用来描述样本集中趋势的,但三者描述的机制和所表达出来的内涵有不小的区别。算数平均数这样一个统计量反映了样本内所有个体的信息,尽管反映的程度因个体在整体中所占比重不同而不同。在政治过程中,算数平均数与完全的平均主义、严格的每人一票、“全民公投”等相对应。中位数指的在是从小到大排序之后的样本序列中,位于中间的数值,它并不能反映所有样本个体的信息,仅仅考虑的是在相对位置上中间的样本的信息。在一个社会中,按照财富和社会地位进行排序位于中间位置的是中产阶级。中产阶级的意见受到重视的社会是一个较为稳定的社会,是一个有了较高发展程度的社会。众数指的则是在样本中出现次数做多的个体。很明显,在政治过程中这是与“少数服从多数”相对应的。出现次数最多的个体信息被表达出来,其他个体的所有信息完全被忽视。那个个体票数最多,它的利益得以实现,而少数人的利益则不能够得到保证。这恰恰证明了所谓民主的局限之一,即“多数人对少数人的暴政”。
    在一个社会里,完全的平均主义会使人们失去进取的动力,“全民公投”的成本极高并且也不能保证个体表达出其真实意愿,因此这并不是理想的政治过程。在改革开放之前实行的计划经济体制最终走下了历史舞台也正是因为我们清楚地认识到了这样的问题;我们反对台湾当局针对台湾是否独立实行“全民公投”也正是基于这一点。那么美国式的民主,即“少数服从多数”是否理想呢?民主是有局限性的,如此的政治过程不能够保护少数人的利益,正是其重要的缺陷之一。况且如果需要政府来保障那些不能通过政治过程实现自身利益的个体,成本极高。相对而言,使中产阶级的利益得以表达,将会形成一个稳定的社会结构,市较为理想的政治过程。人们会有不断进取的心态使自己成为中产阶级,同时最富裕的阶层也受到了一定限制,从而不会凭借其财富垄断社会的公共资源,为整个社会提供了一套阶层之间相互流动的渠道和机制。当然,如此的政治过程仍然是具有一定局限性的。比如仍然会有部分弱势群体的利益得不到保护。但是,相对于“少数服从多数”的政治过程,政府出面保护弱势群体的成本将低得多了。那么我们能不能为社会提供一个最为理想的政治过程呢,哪怕那仅仅是一种理想呢?或许可以。在统计学中,最理想的情况是反映集中趋势的三个统计量相互重合,即算数平均数、中位数和众数相等。这种情况下的社会结构分布可以被看作为正态分布。中产阶级的在数量上占整体的多数,即为富裕与极贫困者皆为少数;中产阶级通过民主的政治过程表达出自身的利益取向;平均看来整个社会在一个较高的发展水平上运行。

    教参上说了他们三者的联系

    “重视理解平均数、中位数与众数的联系与区别。
    描述一组数据的集中趋势,可以用平均数、中位数和众数,它们有各自不同的特点。
    平均数应用最为广泛,用它作为一组数据的代表,比较可靠和稳定,它与这组数据中的每一个数据都有关系,能够最为充分地反映这组数据所包含的信息,在进行统计推断时有重要的作用;但容易受到极端数据的影响。
    中位数在一组数据的数值排序中处于中间的位置,故其在统计学分析中也常常扮演着“分水岭”的角色,人们由中位数可以对事物的大体趋势进行判断和掌控。
    众数着眼于对各数据出现的频数的考察,其大小仅与一组数据中的部分数据有关,当一组数据中有不少数据多次重复出现时,它的众数往往是我们关心的一种统计量。
    在这部分知识的教学中,要注意讲清上述三个量的联系与区别。使学生知道它们都是描述一组数据集中趋势的统计量,但描述的角度和适用范围有所不同,在具体的问题中究竟采用哪种统计量来描述一组数据的集中趋势,要根据数据的特点及我们所关心的问题来确定。”

    有个顺口溜 分析数据平中众,比较接近选平均,相差较大看中位,频数较大用众数;
       所有数据定平均,个数去除数据和,即可得到平均数;大小排列知中位;
       整理数据顺次排,单个数据取中问,双个数据两平均;频数最大是众数

    展开全文
  • python求解中位数、均值、众数

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

    首先定义一个数据,在这里我假定为:

    num=[2,3,2,5,1,0,1,2,9]

    一、求中位数

           中位数(又称中值,英语:Median),统计学中的专有名词,代表一个样本、种群或概率分布中的一个数值,其可将数值集合划分为相等的上下两部分。对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,则中位数不唯一,通常取最中间的两个数值的平均数作为中位数。

           一个数集中最多有一半的数值小于中位数,也最多有一半的数值大于中位数。如果大于和小于中位数的数值个数均少于一半,那么数集中必有若干值等同于中位数。设连续随机变量X的分布函数为F(X),那么满足条件P(X≤m)=F(m)=1/2的数称为X或分布F的中位数。对于一组有限个数的数据来说,其中位数是这样的一种数:这群数据的一半的数据比它大,而另外一半数据比它小。

           计算有限个数的数据的中位数的方法是:把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数,则中间那个数据就是这群数据的中位数;如果数据的个数是偶数,则中间那2个数据算术平均值就是这群数据的中位数。

    import numpy as np
    np.median(num)

    二、求均值

           平均数(英语:Mean,或称平均值)是统计中的一个重要概念。为集中趋势的最常用测度值,目的是确定一组数据的均衡点。算术平均数(或简称平均数)是一组样本x_{1},x_{2},\ldots ,x_{n} 的和除以样本的数量。其通常记作\bar{x}{\bar  {x}}={\frac  {x_{1}+x_{2}+\cdots +x_{n}}{n}}

           例如, 4,36,45,50,75 ,这组数的算术平均数是:{\frac  {4+36+45+50+75}{5}}={\frac  {210}{5}}=42

           在统计中算术平均数常用于表示统计对象的一般水平,它是描述数据集中程度的一个统计量。我们既可以用它来反映一组数据的一般情况,也可以用它进行不同组数据的比较,以看出组与组之间的差别。用平均数表示一组数据的情况,有直观、简明的特点,所以在日常生活中经常用到,如平均的速度、平均的身高、平均的产量、平均的成绩......“ 范围 ” 用于数值型数据,不能用于分类数据和顺序数据。

    import numpy as np
    np.mean(num)
    

    三、求众数

          众数(mode)指一组数据中出现次数最多的数据值。例如{2,3,3,3}中,出现最多的是3,因此众数是3,众数可能是一个数,但也可能是多个数。在离散概率分布中,众数是指概率质量函数有最大值的数据,也就是最容易取様到的数据。在连续概率分布中,众数是指机率密度函数有最大值的数据,也就是机率密度函数的峰值。在统计学上,众数和平均数中位数类似,都是总体随机变量有关集中趋势的重要资讯。在高斯分布正态分布)中,众数位于峰值,和平均数中位数相同。但若分布是高度偏斜分布,众数可能会和平均数、中位数有很大的差异。

           分布中的众数不一定只有一个,若概率质量函数或机率密度函数在x1, x2……等多个点都有最大值,就会有多个众数,最极端的情形是离散型均匀分布,所有的点概率都相同,所有的点都是众数。若机率密度函数有数个局部最大值,一般会将这几个极值都称为众数,此连续机率分布会称为多峰分布(和单峰性相反)。若是对称的单峰分布(例如正态分布),众数和平均数中位数会重合[1]。若一随机变量是由对称的总体中产生,可以用取样的平均值来估计总体的众数。

    方法一:用numpy中建立元素出现次数的索引的方法求众数

    import numpy as np
    c=np.bincount(num)
    np.argmax(c)

    方法二:直接利用scipy下stats模块

    from scipy import stats
    stats.mode(num)[0][0]

     

    展开全文
  • Java||求集合数组中的中位数

    千次阅读 2019-08-03 22:05:44
    中位数: 简单解释就是最中间的那个数,如果集合是奇数个,则中位数是按大小排列最中间那个数,如果集合是偶数个,则中位数就是按大小排列最中间那两个数的平均数。 求解: 先判断这个集合是奇数还是偶数,如果是...
  • 利用SQL求中位数(已修复BUG)

    万次阅读 热门讨论 2019-09-18 16:48:36
    看《SQL进阶教程》,看到用 HAVING 子句进行自连接:求中位数 这一节时对于给出的SQL不是很理解。因此花了一些时间分析了一下。体会贴在此博文中。 HAVING 子句进行自连接:求中位数 中位数是指将集合中的元素按照...
  • 寻找两个正序数组的中位数1、问题分析2、问题解决3、总结 1、问题分析 题目链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/ 具体思路是: 1、 根据两个数组的总长度计算是否是 ...
  • 程序设计-求N个数的中位数(C++)

    万次阅读 2019-02-28 10:19:02
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... /* * 求n个数的中位数 - C++ - by Chimomo ... * 计算有限个数的数据的中位数的方法是:把所有的同类...
  • 求无序数组的中位数(c语言版本)

    千次阅读 2019-03-22 16:06:41
    在面试时,会经常被问道,如何求解一个无序数组的中位数?很多人往往都会第一感觉就是,先将该数组排序,然后找出最中间的那个数,但是这种思路通常的时间复杂度最好是O(nlogn),更糟的情况下会到O(n^2),并不是最优...
  • 计算一串数组的均值、中位数、标准差 #!/usr/bin/env python #-*- coding:utf-8 -*- ''' @author : FIGTHING @file : DataMining.py @function: @software: Pycharm @time : 2019/06/13/15:40 ''' import numpy as...
  • 中位数(C语言)

    万次阅读 2017-06-19 17:50:46
    计算有限个数的数据的中位数的方法是:把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数,则中间那个数据就是这群数据的中位数;如果数据的个数是偶数,则中间那2个数据的算术平均值就是这群数据的中位数...
  • Java实现 LeetCode 480 滑动窗口中位数

    万次阅读 多人点赞 2020-03-19 10:44:44
    480. 滑动窗口中位数 中位数是有序序列最中间的那个数。如果序列的大小是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。 例如: [2,3,4],中位数是 3 [2,3],中位数是 (2 + 3) / 2 = 2.5 给你一个...
  • 什么是中位数? 数值型数组的中位数是在数据排序后位于数组中间项的值。如果数组有偶数个元素,中位数就是最中间的两个数值的平均数。 中位数对于了解“我的值是否位于中间?”非常有用。比如,我在学校的最后...
  • 什么是高位数,中位数,低位数

    千次阅读 2019-10-22 14:15:15
  • Java实现-中位数

    万次阅读 2017-06-18 14:48:42
    中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N/2个数。 您在真实的面试中是否遇到过这个题?  Yes 样例 给出数组[4, 5, 1, 2, 3], 返回 3 给出数组[7, 9, 4, ...
  • pyton构建一个计算列表中位数的函数

    千次阅读 2019-05-14 10:22:49
    中位数为常见的统计量之一,可将一个数集划分为相等的上下两部分。对于元素个数不同的列表而言,中位数的计算方式分为如下两种。 (1)若列表中元素的个数为奇数,则中位数为排序后列表中间位置的那个数。 (2)若...
  • 例如: >>> a = [8, 19, 34, 9, 18] >>> np.median(a) # 得到数组 a 的中位数 18.0 >>> np.quantile(a, 0.25) # 得到数组 a 的上四分位数 9.0 >>> np.quantile(a, 0.5) # 得到数组 a 的中位数 18.0 >>> np.quantile...
  • [CQOI2009]中位数

    千次阅读 2021-02-23 23:50:43
    给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。 输入描述: 第一行为两个正整数n和b ,第二行为1~n 的排列。 输出描述: 输出一个...
  • 从数据流中获取中位数

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

    千次阅读 2017-07-26 10:50:51
    100亿个整数,内存足够,如何找到中位数?内存不足,如何找到中位数? (1)当内存足够时:采用快排,找到第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的中位数(若结果为小数,则保留一位小数)。
  • 统计学第一篇,均值、中位数、众数 均值、中位数、众数是表示一组数据集中趋势的量数,下面以“1,2,3,3,5,7,7,8,9,10”数据集为例 均值,中位数,众数 Type 示例 值 说明 均值(Mean) (1+2+3+3+5+7+7+8...
  • 查找中位数(java 快速排序)

    千次阅读 2016-10-31 16:14:39
    中位数(又称中值,英语:Median),统计学中的专有名词,代表一个样本、种群或概率分布中的一个数值,其可将数值集合划分为相等的上下两部分。对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为...
  • python中获取中位数的两种方法

    千次阅读 2020-09-27 14:12:51
    对列表进行排序,然后根据长度为奇数或者偶数的不同情况计算中位数 def huahua(x): length = len(x) print(length) x.sort() print(x) if (length % 2)== 1: z=length // 2 y = x[z] else: y = (x[length//...
  • 中位数

    千次阅读 2013-03-19 10:23:57
    中位数(Medians)统计学名词,是指将统计总体当中的各个变量值按大小顺序排列起来,形成一个数列,处于变量数列中间位置的变量值就称为中位数,用Me表示。当变量值的项数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) ...
  • Java实现 LeetCode 295 数据流的中位数

    万次阅读 多人点赞 2020-03-05 17:03:42
    295. 数据流的中位数 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构: ...
  • BFPRT(中位数中位数)算法

    千次阅读 2017-10-09 16:05:05
    BFPRT 算法又称为 “中位数中位数算法”,该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 在1973年提出,最坏时间复杂度为 O(n) TOP-K问题
  • python求均值、中位数、众数的方法

    万次阅读 多人点赞 2018-05-26 16:18:58
    首先需要数据源,这里随便写了一个:nums = [1,2,3,4]求均值和中位数均可以使用numpy库的方法: #均值 np.mean(nums) #中位数 np.median(nums)求众数方法一:在numpy中没有直接的方法,但是也可以这样实现:import ...
  • 中位数、众数和均值的关系

    万次阅读 2016-01-23 16:35:44
    中位数、众数和均值都是描述数据集中趋势的统计量,他们各有特点。例如,对于某种商品的各种售价,中位数处在中间的价格,大于和小于中位数的价格各为一半;众数为众多价格中出现频数最多的那个价格;而均值在大部分...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,485,832
精华内容 994,332
关键字:

中数是中位数吗