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

    2014-05-11 11:33:00
    求中位数 题目描述 输入n和n个数,求大于中位数的数据个数。(n小于50) 中位数是把一列数从小到大排列后,中间的那个数!如果那一列数是偶数,就取中间两个数的平均数! 例如: 第1组数:1、2、3、6、7的中位数...

    求中位数 

    题目描述

     

    输入n和n个数,求大于中位数的数据个数。(n小于50)
    中位数是把一列数从小到大排列后,中间的那个数!如果那一列数是偶数,就取中间两个数的平均数!
    例如:
    第1组数:1、2、3、6、7的中位数是3。 
    第2组数:1、2、3、5的中位数是2.5。				

     

    输入描述

     

    输入正整数n和n个实数				

     

    输出描述

     

    1.输出中位数保留小数1位。中位数输出占一行。
    2.输出大于中位数的数据个数占一行。			

     

    样例输入

     

    4  1  2  3  5        

     

    样例输出

     

    2.5
    2            

    转载于:https://www.cnblogs.com/lpjia/p/3721500.html

    展开全文
  • 在二分法查找中,求中位数的一些坑(左中位数和右中位数)@TOC 使用二分法查找时,我们经常会通过求中位数,来判断与目标值的大小关系。 但是一定要注意!!!若在选择选择中位数时要进行取整迭代,就要选择合适的中...

    在二分法查找中,求中位数的一些坑(左中位数和右中位数)
    使用二分法查找时,我们经常会通过求中位数,来判断与目标值的大小关系。
    但是一定要注意!!!若在选择选择中位数时要进行取整迭代,就要选择合适的中位数求法,不能只简单的使用
    mid=(left+right)>>>1;,会导致出现死循环的情况。
    常见的有取左中位数和右中位数两种方法,代码如下:

    //左中位数求法
    mid = left + (right - left + 1)>>>1;
    //右中位数求法
    mid = (left + right + 1) >>>1;
    
    展开全文
  • 求中位数,快速选择算法

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

    实验五    输油管道问题的设计与实现

    [实验目的]

    1、掌握分治算法的基本原理

    2、利用分治策略编程解决输油管道问题

    [实验内容]

    问题描述

    某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?

    1.请给出分析与解答;

    2.给出代码和运行结果;

    3.估算算法的时间复杂度。

    关于确定主管道的最优位置:由于主管道是由东向西,则主管道的铺设位置只和各油井位置的y坐标有关,要求的最优主管道的位置y坐标应是各个油井y坐标的中位数。

    反证法证明之:

    油井数目为奇数:假设主管道的最优位置y坐标值为y_ave,不是各个油井位置y坐标的中位数y_mid,我们可以假设y_ave>y_mid,y坐标小于y_ave的油井数目为m,y坐标大于y_ave的油井数目为n,显然有m>n。当我们将主管道位置下移距离x时(假设此时仍满足y_ave>=y_mid),各油井到主管道之间的输油管道长度总和应增加nx-mx,显然nx-mx<0(m>n),即存在一个比_ave更优的位置使得各油井到主管道之间的输油管道长度总和更小,这与假设矛盾。当y_ave>y_mid时,同理可证。

    油井数目为偶数时:同理可证 。

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

    随机选择算法求中位数:如果是奇数个点,就是中间那个,如果是偶数个点,下面代码求的是中间靠左的那个数,当然油田放在中间靠右的那个也可以,各油井到主管道之间的输油管道长度总和是一样的,随机选择算法和快排差不多,先让第一个数找到对应的位置,比它小的放左边,比它大的放它右边,然后如果被排序的位置是中位数,则返回之,如果中位数的位置小于这个位置,就对左区域进行随机选择算法,反之则对右区域进行随机选择算法。

    测试数据1:

    5

    1 2

    2 2

    1 3

    3 -2

    3 3

    运行结果截图:

     

    测试数据2:

    6
    1 6
    2 -2
    1 3
    3 -2
    3 3
    1 1

    运行结果截图:

     

    时杂度分析:算法的时间复杂度为O(n).

    获取源代码请阅读全文:https://ai.52learn.online/525

    展开全文
  • javascript中怎么实现求一个数组的中位数,求中位数的方式怎么实现的呢?
  • 有序数组求中位数问题

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                    1、有两个已排好序的数组A和B,长度均为n,找出这两个数组合并后的中间元素,要求时间代价为O(logn)。
    2、假设两个有序数组长度不等,同样的求出中位数。
    一:解析: 这个题目看起来非常简单。第一题的话: 假设数组长度为n, 那么我就把数组1和数组2直接合并,然后再直接找到中间元素。对于这样的方案,第一题和第二题就没有什么区别了。这样的话时间复杂度就是O(n)。通常在这样的情况下,那些要求比较高的面试官就会循循善诱道:“你还有更好的办法吗?” 如果比线性更高效,直接能想到的就是对数了O(log(n)),这个时间复杂度在这里可能吗? 当然还是可能的。
    算法导论上面的分析是这样的:
    Say the two arrays are sorted and increasing, namely A and B.
    It is easy to find the median of each array in O(1) time.
    Assume the median of array A is m and the median of array B is n. Then,
    1、If m==n,then clearly the median after merging is also m,the algorithm holds.
    2、If m<=n,then reserve the half of sequence A in which all numbers are greater than m,also reserve the half of sequence B in which all numbers are smaller than n.
    Run the algorithm on the two new arrays。
    3、If m>n,then reserve the half of sequence A in which all numbers are smaller than m,also reserve the half of sequence B in which all numbers are larger than n.
    Run the algorithm on the two new arrays。
    Time complexity: O(logn)
    下面,我们来画个图,分析一下这个思路:

    我们先来分析看看: 想到对数的效率,首先想到的就是二分查找,对于这个题目二分查找的意义在哪里呢?
    我们找到了A[n/2] 和 B[n/2]来比较,
    1、如果他们相等,那样的话,我们的搜索结束了,因为答案已经找到了A[n/2]就肯定是排序后的中位数了。
    2、如果我们发现B[n/2] > A[n/2],说明什么,这个数字应该在 A[n/2]->A[n]这个序列里面, 或者在 B[1]-B[n/4]这里面。 或者,这里的或者是很重要的, 我们可以说,我们已经成功的把问题变成了在排序完成的数组A[n/2]-A[n]和B[0]-B[n/2]里面找到合并以后的中位数, 显然递归是个不错的选择了。
    3、如果B[n/2] < A[n/2]呢?显然就是在A[0]-A[n/2]和B[n/2]-B[n]里面寻找了。

    在继续想, 这个递归什么时候收敛呢?当然一个case就是相等的值出现, 如果不出现等到这个n==1的时候也就结束了。
    照着这样的思路, 我们比较容易写出如下的代码, 当然边界的值需要自己思量一下(递归代码如下):
    // 两个长度相等的有序数组寻找中位数int Find_Media_Equal_Length(int a[] , int b[] , int length){    if(length == 1)    {        return a[0] > b[0] ? b[0] : a[0];    }    int mid = (length-1)/2;   //奇数就取中间的,偶数则去坐标小的    if(a[mid] == b[mid])        return a[mid];    else if(a[mid] < b[mid])    {        return Find_Media_Equal_Length(&a[length-mid-1] , &b[0] , mid+1);    //偶数则取剩下的length/2,奇数则取剩下的length/2+1        //return Find_Media_Equal_Length(a+length-mid-1 , b , mid+1);    }    else    {        return Find_Media_Equal_Length(&a[0] , &b[length-mid-1] , mid+1);        //return Find_Media_Equal_Length(a , b+length-mid-1 , mid+1);    }}
    非递归代码如下:
    // 非递归代码int Find_Media_Equal_Length(int a[] , int b[] , int length)int mid; while(1) {  if(length == 1)  {   return a[0] > b[0] ? b[0] : a[0];  }  mid = (length-1)/2;  if(a[mid] == b[mid])   return a[mid];  else if(a[mid] < b[mid])   a = a + length - mid - 1;    // a数组的后半部分  else   b = b + length - mid - 1;    // b数组的后半部分  length = mid + 1; }}
    二:马上有人说那不定长的怎么办呢?一样的,我们还是来画个图看看:

    一样的, 我们还是把这个两个数组来比较一下,不失一般性,我们假定B数组比A数组长一点。A的长度为n, B的长度为m。比较A[n/2]和B[m/2] 时候。类似的,我们还是分成几种情况来讨论:
    a、如果A[n/2] == B[m/2],那么很显然,我们的讨论结束了。A[n/2]就已经是中位数,这个和他们各自的长度是奇数或者偶数无关。
    b、如果A[n/2]  <   B[m/2],那么,我们可以知道这个中位数肯定不在[A[0]---A[n/2])这个区间内,同时也不在[B[m/2]---B[m]]这个区间里面。这个时候,我们不能冲动地把[A[0]---A[n/2])和[B[m/2]---B[m]]全部扔掉。我们只需要把[B[m-n/2]---B[m]]和[A[0]---A[n/2])扔掉就可以了。(如图所示的红色线框),这样我们就把我们的问题成功转换成了如何在A[n/2]->A[n]这个长度为 n/2 的数组和 B[1]-B[m-n/2]这个长度为m-n/2的数组里面找中位数了,问题复杂度即可下降了。
    c、只剩下A[n/2] > B[m/2],和b类似的,我们可以把A[n/2]->A[n]这块以及B[1]->B[n/2]这块扔掉了就行,然后继续递归。
    我们也可以写出如下的代码:
    // 两个长度不相等的有序数组寻找中位数int Find_Media_Random_Length(int a[] , int lengtha , int b[] , int lengthb)int mida = lengtha/2int midb = lengthb/2int l = (mida <= midb) ? mida : midb; if(lengtha == 1) {  if(lengthb % 2 == 0)  {   if(a[0] >= b[midb])    return b[midb];   else if(a[0] <= b[midb-1])    return b[midb-1];   return a[0];  }  else   return b[midb]; } else if(lengthb == 1) {  if(lengtha % 2 == 0)  {   if(b[0] >= a[mida])    return a[mida];   else if(b[0] <= a[mida-1])    return a[mida-1];   return b[0];  }  else   return a[mida]; } if(a[mida] == b[midb])  return a[mida]; else if(a[mida] < b[midb])  return Find_Media_Random_Length(&a[mida] , lengtha-l , &b[0] , lengthb-l); else  return Find_Media_Random_Length(&a[0] , lengtha-l , &b[midb] , lengthb-l);}
    举例如下:
    A:1、2、8、9、10
    B:1、2、3、4、11
    第一次:
    A:1、2、{8}、9、10
    B:1、2、{3}、4、11
    因为8>3,所以第二次:
    A:1、{2}、8
    B:3、{4}、11
    因为2<4,所以第三次:
    A:{2}、8
    B:{3}、4
    因为2<3,所以第四次:
    A:{8}
    B:{3}

    再举一个简单的例子:
    A: 1 3 5 7 9
    B: 2 4 6 8 10
    结果我们都知道是5(下中位数)。
    第一步:取5 和 6比较,发现5<6,则在 7 9 2 4中寻找吗?
    偶数的情况类似:
    A: 1 3 5 7 9 11
    B: 2 4 6 8 10 12
    第一步:取5 和 6比较,发现5<6,则在 7 9 11 2 4中寻找吗?
    个人认为取一半的时候一定需要包含用于比较的两个中位数(无论奇偶)。
    就是说上面的两个例子第一步之后:
    在A:5 7 9    B:2 4 6中继续找
    在A:5 7 9 11    B:2 4 6中继续找
    但这样导致新的问题是:新的数组A和B数字个数不一致了!
    办法是: 在递归的过程中,当数组中的元素是偶数时,在一个数组中取上中位数,在另一个数组中取下中位数,并且在整个过程中保持不变。在哪个数组中去上中位数,就一直在那个数组中取上中位数,反之亦然。奇数时的情形依旧。
    这也就解释了为什么代码中a[mid]<b[mid] 的时候,a数组的开始位置会是: a[length-mid-1]

               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • js求中位数函数

    千次阅读 2020-05-08 14:40:41
    let _median = arr => { arr.sort(); //求中位数 if (arr.length % 2 == 0) { return (arr[arr.length / 2 - 1] + arr[arr.length / 2]) / 2; } else { ...
  • python之求中位数

    万次阅读 2018-04-26 20:23:28
    求中位数 给你一个整数列表L, 输出L的中位数(若结果为小数,则保留一位小数)。 例如: L=[0,1,2,3,4] 则输出:2 2.说明 如果列表有奇数个整数,则输出中间那个 如果列表有偶数个整数,则输出中间两个...
  • 求中位数

    2015-10-26 21:03:15
    /在网上找了好久,没有找到求一个行列均递增二维矩阵的中位数算法,于是自己花了几天的时间去摸索一下求一个数组的中位数算法,本算法不只是求中位数,可以求出你想求/////的///第K小的元素, //不废话,上代码。。 ...
  • Python求中位数 每个人都像一辆车。档次有高低,性能有好坏,颜值有高低。但上了路,总归是要向前开。 中位数是一个可将数值集合划分为相等的上下两部分的一个数值。 如果列表数据的个数是奇数,则列表中间那个...
  • 大数据求中位数(插值计算)

    千次阅读 2020-06-15 11:48:24
    常规(数据量不大的情况)求中位数和基于插值计算求中位数的方法 在学数学时我们学到过求中位数的方法,在数据个数为偶数时找最中间的两个数然后求平均数如果数据个数为奇数时则只需找数据个数一半的那位上的数字...
  • mySQL求中位数、众数

    千次阅读 2020-01-13 18:13:28
    mysql 取中位数、众数 -- 求众数 SELECT score, count(score) from scores GROUP BY score HAVING count(score) >= (SELECT max(a.b) from (SELECT count(score) as b from scores ...-- 求中位数 -- 申明...
  • 利用SQL求中位数(已修复BUG)

    千次阅读 热门讨论 2019-09-18 16:48:36
    看《SQL进阶教程》,看到用 HAVING 子句进行自连接:求中位数 这一节时对于给出的SQL不是很理解。因此花了一些时间分析了一下。体会贴在此博文中。 HAVING 子句进行自连接:求中位数 中位数是指将集合中的元素按照...
  • 无序数组求中位数

    千次阅读 2018-12-07 16:34:46
    长度为 n 的无序数组,求中位数,如何尽快的估算出中位数,算法复杂度是多少? 算法 1(建立最小堆): 如果数组中元素有奇数个,可以采用这种算法: 步骤 1 :可以将数组的前 (n+1)//2 个元素,建立 1 个最小堆; ...
  • 中位数中位数是一组数字中的中间数。此代码计算包含数字的列表的中位数:我们定义一个数字列表并计算列表的长度。要查找中位数,我们首先使用sort()函数按升序排序列表。现在我们通过检查剩余数量来检查数字是偶数...
  • 不排序求中位数

    千次阅读 2014-02-22 10:10:38
    不排序求中位数 /* 一组数的中位数,就是把一组数从小到大排好后位居中间的 那一个;如果有奇数个数,那么中位数就是中间的那个;如果 有偶数个数,那么中位数就是中间两个数的平均数。 那么有没有办法不用排序就...
  • O(n)的时间复杂度求中位数

    千次阅读 2020-09-26 14:45:14
    O(n)的时间复杂度求中位数 O(n)中位数问题是指:在O(n)的时间复杂度内找到一个无序序列的中位数。 在开始O(n)时间复杂度求中位数之前,先手写一下快速排序。 快速排序的实现 Reference: 快速排序|菜鸟教程 白话经典...
  • File name:求中位数.cpp Author:杨柳 Date:2017/5/25 IDE:DEV-c++ 思想:把无序数组排好序,取出中间的元素 */ #include #include using namespace std; #define MAX 100 int array[MAX],arr[MAX]; int result=0;/...
  • 双堆求中位数

    千次阅读 2015-03-31 10:40:06
    双堆求中位数 算法描述: 1、创建两个堆(一个小根堆、一个大根堆),堆大小至少为给定数据个数的一半,向上取整; 2、假定变量mid用来保存中位数,取定第一个元素,赋值给mid,即作为初始的中位数; 3、依次...
  • 二分法求中位数(偶数也行)

    千次阅读 2017-12-30 22:18:05
    看到一个很有意思的题,用二分法求中位数,网络上都是求奇数个整数的中位数,所以写了一个偶数个整数求中位数的代码,最后的输出如果有必要也可以用%f输出(l+r)/2.0 问题描述:(求中位数) 给定n(n 为小于1000)...
  • 无序数组中求中位数

    千次阅读 2017-06-08 16:34:15
    题目现有一些随机生成的数字要将其依次传入,请设计一个高效算法,对于每次传入一个数字后,算出当前所有传入数字的中位数。(若传入了偶数个数字则令中位数为第n/2小的数字,n为已传入数字个数)。 给定一个int数组A...
  • #定义一个函数求中位数 #参数:不定长参数(元组的形式存储) def median(*a): #*a是不定长参数,a以一个元组的形式储存 l=sorted(a) #sorted(a)对列表进行排序,结果返回一个列表 index=len(l)//2 #获取中间值...
  • Problem G: 求中位数

    千次阅读 2014-12-13 13:29:04
    Problem G: 求中位数 Time Limit: 1 Sec Memory Limit: 16 MB Submit: 652 Solved: 217 [Submit][Status][Web Board] Description 中位数(Medians)是一个统计学名词,是指将统计总体当中的各个数据...
  • 给定一个整数序列,求中位数。如果序列个数为奇数,中位数为升序的中间位置,如果是偶数,这位升序的中间两个数的平均值。 输入: 输入包含多组测试数据,每一组第一行为n(n&lt;104)表示这个序列的个数,接下来...
  • POJ 2388 求中位数 qsort用法

    千次阅读 2012-02-11 13:23:29
    这题就是求中位数,直接用qsort排序取中,算法复杂度为O(NlogN) 当然求中位数的最优算法是O(N)的Select算法 Source Code Problem: 2388   User: yangliuACMer Memory: 284K   Time: ...
  • C++实现求中位数

    2020-03-14 20:04:03
    给出一组无序整数,中位数,如果最中间两个数的平均数,向下取整即可(不需要使用浮点数) 输入输出格式 输入描述: 该程序包含多组测试数据,每一组测试数据的第一行为N,代表该组测试数据包含的数据个数,1&...
  • mysql 求中位数、四分位数

    千次阅读 2019-08-28 19:51:41
    当记录是偶数时,中位数是中间两个数的平均 SELECT GROUP_CONCAT( id ), avg( `VALUE` ) FROM (#第二层开始 SELECT id, @INDEX := @INDEX + 1 AS myindex, `VALUE` -- myindex代表的是这一列数,@index是...
  • 编译过了,求中位数的中位数结果不对 ``` #include #include void paixu(int *a,int p,int r) { int b; for(int i=p;i;i++) { for(int j=r;j>i;j--) { if(a[j]>a[j-1]) { b=a[j]; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,315
精华内容 6,526
关键字:

求中位数