精华内容
下载资源
问答
  • 算法 - 求n个数的中位数(C++)

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

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    /*
     * 求n个数的中位数 - C++ - by Chimomo
     *
     * 对于一组有有限个数的数据来说,它们的中位数是这样的一种数:这群数据里的一半的数据比它大,而另外一半数据比它小。
     * 计算有限个数的数据的中位数的方法是:把所有的同类数据按照大小的顺序排列。
     * 如果数据的个数是奇数,则中间那个数据就是这群数据的中位数;
     * 如果数据的个数是偶数,则中间那2个数据的算术平均值就是这群数据的中位数。
     */
    
    #include <iostream>
    #include <cassert>
    #include <stack>
    #include <math.h>
    
    using namespace std;
    
    int QuickSortOnce(int a[], int low, int high) {
        // 将首元素作为枢轴。
        int pivot = a[low];
        int i = low, j = high;
    
        while (i < j) {
            // 从右到左,寻找首个小于pivot的元素。
            while (a[j] >= pivot && i < j) {
                j--;
            }
    
            // 执行到此,j已指向从右端起首个小于或等于pivot的元素。
            // 执行替换。
            a[i] = a[j];
    
            // 从左到右,寻找首个大于pivot的元素。
            while (a[i] <= pivot && i < j) {
                i++;
            }
    
            // 执行到此,i已指向从左端起首个大于或等于pivot的元素。
            // 执行替换。
            a[j] = a[i];
        }
    
        // 退出while循环,执行至此,必定是i=j的情况。
        // i(或j)指向的即是枢轴的位置,定位该趟排序的枢轴并将该位置返回。
        a[i] = pivot;
    
        return i;
    }
    
    void QuickSort(int a[], int low, int high) {
        if (low >= high) {
            return;
        }
    
        int pivot = QuickSortOnce(a, low, high);
    
        // 对枢轴的左端进行排序。
        QuickSort(a, low, pivot - 1);
    
        // 对枢轴的右端进行排序。
        QuickSort(a, pivot + 1, high);
    }
    
    int EvaluateMedian(int a[], int n) {
        QuickSort(a, 0, n - 1);
    
        if (n % 2 != 0) {
            return a[n / 2];
        } else {
            return (a[n / 2] + a[n / 2 - 1]) / 2;
        }
    }
    
    int main() {
        int a[9] = {-5, 345, 88, 203, 554, 1, 89, 909, 1001};
        cout << EvaluateMedian(a, 9) << endl;
        return 0;
    }
    
    // Output:
    /*
    203
    
    */
    

     

    展开全文
  • 中位数

    千次阅读 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求均值、中位数、众数的方法

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

    首先需要数据源,这里随便写了一个:

    nums = [1,2,3,4]

    • 均值中位数均可以使用numpy库的方法:
    import numpy as np
    
    #均值
    np.mean(nums)
    #中位数
    np.median(nums)

    • 众数方法一
    在numpy中没有直接的方法,但是也可以这样实现:

    import numpy as np
    
    counts = np.bincount(nums)
    #返回众数
    np.argmax(counts)
        其中np.bincount方法返回了一个长度为nums最大值的列表,列表中的每个值代表其索引位数值出现在nums中的次数,例如

    返回[2,1,0],代表0在nums中出现2次,而1在nums中出现1次,3在nums中没有出现。

        然后再使用np.argmax就能得到众数啦。但是,由于索引值是从0开始的,所以这种求众数的方法只能用在非负数据集。


    • 众数方法二——直接利用scipy下stats模块【推荐】:
    from scipy import stats
    
    stats.mode(nums)[0][0]




    展开全文
  • 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) ...

    关于求解中位数,我们知道在Python中直接有中位数处理函数(mean),比如在Python中求解一个中位数,代码很简单。

    Python计算中位数

    import numpy as np
    
    nums = [1.1,2.2,3.3,4.4,5.5,6.6]
    

    均值

    np.mean(nums)
    

    中位数

    np.median(nums)
    

    在hive中没有直接提供相关的mean函数,但官方提供了两个UDAF,percentile和percentile_approx。

    我们看下官方是怎么说的

    DOUBLEpercentile(BIGINT col, p)Returns the exact pthpercentile of a
    column in the group (does not work with floating point types). p must
    be between 0 and 1. NOTE: A true percentile can only be computed for
    integer values. Use PERCENTILE_APPROX if your input is non-integral.

    arraypercentile(BIGINT col, array(p1[, p2]…))Returns the exact
    percentiles p1, p2, … of a column in the group (does not work with
    floating point types). pimust be between 0 and 1. NOTE: A true
    percentile can only be computed for integer values. Use
    PERCENTILE_APPROX if your input is non-integral.

    DOUBLEpercentile_approx(DOUBLE col, p [, B])Returns an approximate
    pthpercentile of a numeric column (including floating point types) in
    the group. The B parameter controls approximation accuracy at the
    cost of memory. Higher values yield better approximations, and the
    default is 10,000. When the number of distinct values in col is
    smaller than B, this gives an exact percentile value.

    arraypercentile_approx(DOUBLE col, array(p1[, p2]…) [, B])Same as
    above, but accepts and returns an array of percentile values instead
    of a single one.

    请注意,官方文档上说了一句话:NOTE: A true percentile can only be computed for integer values. UsePERCENTILE_APPROX if your input is non-integral.

    也就是说,真正的中位数只能用percentile来计算,输入需要为整数类型,使用percentile_approx(输入为浮点型)计算得到的并不是真正的中位数,也就是所说的近似中位数,经过大量数据验证,有时候这个近似中位数和真正的中位数差别还是很大的。

    如何对有小数的数据求取中位数呢?

    可以把小数转换为整数,然后再求取中位数(如先✖️乘10000)

    sparksql中也是如此求取中位数的,赶快去试一试吧!

    展开全文
  • 从数据流中获取中位数

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

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

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

    千次阅读 2016-02-01 16:18:57
    信息学竞赛总是时不时与数学产生微妙的关系,中位数及带权中位数问题有时常常成为解题的关键,今日有时间,所以梳理一下。 先从一到简单的题看起: 士兵站队问题 在一个划分成网格的操场上,n个士兵散乱地站在...
  • Python计算中位数 numpy.median

    万次阅读 多人点赞 2017-07-04 17:46:48
    计算沿指定轴的中位数 返回数组元素的中位数其函数接口为:median(a, axis=None, out=None, overwrite_input=False, keepdims=False)其中各参数为: a:输入的数组; axis:计算哪个轴上的中位数,比如...
  • 41.1 数据流中的中位数 题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后...
  • 中位数

    千次阅读 2018-12-30 22:56:00
    中位数定义:一组数据按从小到大的顺序依次排列,处在中间位置的一个数 (或最中间两个数据的平均数). 给出一组无序整数,求出中位数,如果求最 中间两个数的平均数,向下取整即可(不需要使用浮点数) 输入描述: ...
  • 无序数组中求中位数

    千次阅读 2017-06-08 16:34:15
    题目现有一些随机生成的数字要将其依次传入,请设计一个高效算法,对于每次传入一个数字后,算出当前所有传入数字的中位数。(若传入了偶数个数字则令中位数为第n/2小的数字,n为已传入数字个数)。 给定一个int数组A...
  • Java实现 LeetCode 480 滑动窗口中位数

    万次阅读 多人点赞 2020-03-19 10:44:44
    480. 滑动窗口中位数 中位数是有序序列最中间的那个数。如果序列的大小是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。 例如: [2,3,4],中位数是 3 [2,3],中位数是 (2 + 3) / 2 = 2.5 给你一个...
  • 中位数计算

    千次阅读 2016-09-29 18:24:07
    题目中位数计算。选择你熟悉的编程语言实现教材P31上公式(2.3)的算法,用于估算大量数据的中位数。下载测试数据文件(1百万条数据,中位数为49899),选择不同的区间大小(width),考察计算结果与真实中位数的...
  • javascript中怎么实现求一个数组的中位数,求中位数的方式怎么实现的呢?
  • 数据流中的中位数

    千次阅读 2018-07-02 11:28:58
    题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。由于...
  • java 计算中位数方法

    千次阅读 2019-01-04 15:51:14
    最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个 先说说什么是中位数中位数就是中间的那个数, 如果一个集合是奇数个,那么中位数就是按大小排列...
  • 文章目录算数平均数、中位数、众数和几何平均数 算数平均数、中位数、众数和几何平均数 统计数据时经常用到的几种数的比较: 算数平均数 中位数 众数 几何平均数 英文名 Arithmetic mean Median Mode ...
  • 代码实现求三个数中的中位数

    千次阅读 2019-07-14 18:21:41
    1.中位数举例 给定一组数arr1 = [1,3,0,2,6](奇数的情况)求其中位数 对arr1根据数值大小重新排列:arr1_new = [0,1,2,3,6] 因此,arr1的中位数为2(2在中间位置) 给定一组数arr2 = [1,3,0,2,6,5](偶数的情况...
  • C语言计算平均数/众数/中位数

    千次阅读 2019-12-18 16:50:57
    1)计算平均数/众数/中位数 在调查数据分析(Survey data analysis)中经常需要计算平均数、中位数和众数。用函数编程计算40个输入数据(是取值1—10之间的任意整数)的平均数(Mean)、中位数(Median)和众数(Mode...
  • Java实现 LeetCode 295 数据流的中位数

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

    千次阅读 2020-03-14 18:51:32
    题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。 关于中位数:...
  • [CQOI2009]中位数

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

    万次阅读 2017-07-11 15:12:56
    分析:于是此题就转化为了求中位数,关于求中位数,可以先排序,然后中间那个就是所求,但是为了体现分治的思想,同时追求更高的效率,于是本次用随机选择算法,随机选择算法和快速排序有点像。 随机选择算法求中位...
  • 二分法找中位数

    千次阅读 2017-09-23 21:27:01
    Name: 中位数median Author: 巧若拙 Description: 描述 给定n(n为奇数且小于1000)个整数,整数的范围在0-m(0^31)之间,请使用二分法求这n个整数的中位数。 所谓中位数,是指将这n个数排序之后,排在正中间...
  • BFPTR算法求n个数中第k大(即第n-1-k小)的数,其思想是基于快速排序中对Partion的pivot值进行优化,快速排序中每一趟快排的pivot的选取一般是数组的首项或者尾项(数值比较随机),而BFPTR是每次选择5分中位数...
  • 中位数的性质

    千次阅读 2017-10-10 19:27:51
    1、中位数的性质  给定一个数列,中位数有这样的性质 :所有数与中位数的绝对差之和最小 2、中位数性质的简单证明  首先,给定一个从小到大的数列x1,x2,……,xn,设x是从x1到xn与其绝对差之和最小的数...
  • OpenJ_Bailian - 4013 中位数

    千次阅读 2020-04-21 20:37:09
    中位数定义:一组数据按从小到大的顺序依次排列,处在中间位置的一个数或最中间两个数据的平均值(如果这组数的个数为奇数,则中位数为位于中间位置的那个数;如果这组数的个数为偶数,则中位数是位于中间位置的两个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 142,804
精华内容 57,121
关键字:

中位数