找出未排序整数数组的中位数

题目- 中位数

给定一个未排序的整数数组,找到其中位数。

中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第 N/2 个数。

示例

给出数组[4, 5, 1, 2, 3], 返回 3

给出数组[7, 9, 4, 5],返回 5

分析

简单的思路就是先排序,然后根据中位数规则取中位数

想想,能不能不排序直接取中位数?或者排序的同时取中位数。

排序可以用哪些方法? 参考:常见排序算法的时间复杂度,空间复杂度

 

Just Try

请你自动动手试一下:在线编程环境

想想有没有其他思路?

想想时间和空间复杂度,能否优化一下

真的做不到么?

let you think, think makes you happy!

 

参考答案

选择排序的实现如下:

function algorithm(arr){
  let  k=0;
  for(let i=0; i< Math.ceil(arr.length/2); i++){
    for(let j=i+1; j< arr.length; j++){
      if(arr[i] > arr[j]){
        k = arr[j]
        arr[j] = arr[i]
        arr[i] = k
      }
    }
  }
  if(arr.length%2==0)
    return arr[arr.length/2-1]
  if(arr.length%2==1)
    return arr[Math.floor(arr.length/2)]
}
function main(param) {
  console.show("参数:" + param, "结果:" + algorithm(param))
  console.show(testPerformance(algorithm, param))
}
main([4, 5, 1, 2, 3])
main([7, 9, 4, 5])

这种双重循环的代码唯一的缺点就是时间复杂度高,只是外层循环减少了一半而已,时间复杂度o(n/2*log(n)),应该有更好的办法来做

请你自动动手试一下:在线编程环境

冒泡排序

function algorithm(arr){
  let  k=0;
  for(let i=0; i< Math.ceil(arr.length/2); i++){
    for(let j=0; j< arr.length-i; j++){
      if(arr[j] > arr[j+1]){
        k = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = k
      }
    }
  }
  if(arr.length%2==0)
    return arr[arr.length/2-1]
  if(arr.length%2==1)
    return arr[Math.floor(arr.length/2)]
}

 

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » 找出未排序整数数组的中位数

赞 (2) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏