javascript中怎么实现求一个数组的中位数,求中位数的方式怎么实现的呢?

javascript中怎么实现求一个数组的中位数,求中位数的方式怎么实现的呢?

6个回答

中位数即是排过序后的处于数组最中间的元素。 不考虑数组长度为偶数的情况。设集合元素个数为n。

简单的想了下:
思路1) 把无序数组排好序,取出中间的元素
时间复杂度 采用普通的比较排序法 O(N*logN)
如果采用非比较的计数排序等方法, 时间复杂度 O(N), 空间复杂度也是O(N).

思路2)
2.1)将前(n+1)/2个元素调整为一个小顶堆,
2.2)对后续的每一个元素,和堆顶比较,如果小于等于堆顶,丢弃之,取下一个元素。 如果大于堆顶,用该元素取代堆顶,调整堆,取下一元素。重复2.2步

2.3) 当遍历完所有元素之后,堆顶即是中位数。

思路3) 熟话说,想让算法跑的更快,用分治!
快速排序之所以得名"快排",绝非浪得虚名!因为快排就是一种分治排序法!
同样,找中位数也可以用快排分治的思想。具体如下:
任意挑一个元素,以改元素为支点,划分集合为两部分,如果左侧集合长度恰为 (n-1)/2,那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧,反之,中位数在左侧。 进入相应的一侧继续寻找中位点。
这种方法很快,但是在最坏的情况下时间复杂度为O(N^2), 不过平均时间复杂度好像是O(N)。

思路4) 快排的方法存在不确定性,导致其最坏和最好的时候差别很大, 那么有没有一种确定性的方法呢? 答案是有的
貌似算法导论里有讲到. 这里我就先不深究了, 可以参考如下的文章,
O(n)时间快速选择
http://www.shadowxh.com/?p=598
以及本文的别人的评论

qq_41133921
qq_41133921 数组名加数组的要取到值的下标,从0开始
大约 2 年之前 回复
sunny_desmond
carrykingdow 回复dabocaiqq: 哈哈哈 你可真皮~~
大约 2 年之前 回复
dabocaiqq
穷在人世中少你左右我想我连什么价值也没有 说的很对,但是我不会给你任何c币的。
大约 2 年之前 回复

有那么麻烦?计算一下数组长度,除以2为整数的话,就取下标为(长度/2)和(长度/2-1)的值相加除以2,不为整数就向下取整,取下标为这个数的值

计算一下数组长度,除以2为整数的话,就取下标为(长度/2)和(长度/2-1)的值相加除以2,不为整数就向下取整,取下标为这个数的值

caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 这个得先排序吧。
大约 2 年之前 回复
qq_37524684
子幽
大约 2 年之前 回复

请后台互相调用接口,交互json或者报文格式

dabocaiqq
穷在人世中少你左右我想我连什么价值也没有 什么乱七八糟的,不可能给你任何c币,你死心吧。
大约 2 年之前 回复
var arr = [2,5,1,8,3,7,11,9];
arr.sort(function(a,b){return a-b;});
var l = arr.length-1;
var n = Math.floor(l/2);
var mid = (arr[n]+arr[l-n])/2;
alert(mid);

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐