无序数组取中位数

2021-01-18 01:13

阅读：725

标签：dia 部分 == 元素 poll static htm add class

最暴力的 - 先排序

快一点的 - 快排，任选一个数，小的放前面，大的放后面，如果左部分的数量正好是（n-1）/ 2 那支点就找到了。否则的话，就继续找。

优雅的 - 构建一个最小堆，用前（n+1）/ 2 个元素构建一个最小堆，将其余元素尝试向里插入，比堆顶小的扔了，比堆顶大的留下，最后的队形就是中位数了。

public static double median(int[] array){
    int heapSize = array.length/2 + 1;
    PriorityQueue heap = new PriorityQueue(heapSize);
    for(int i=0; i){
        heap.add(array[i]);
    }
    for(int i=heapSize; i){
        if(heap.peek()array[i]){
            heap.poll();
            heap.add(array[i]);
        }
    }
    if(array.length % 2 == 1){
        return (double)heap.peek();
    }
    else{
        return (double)(heap.poll()+heap.peek())/2.0;
    }
}

参考： https://www.cnblogs.com/shizhh/p/5746151.html

无序数组取中位数

标签：dia 部分 == 元素 poll static htm add class

原文地址：https://www.cnblogs.com/Fivee/p/12915922.html

上一篇：JavaScript 浮点数陷阱以及解法

下一篇：Java - 通过数据结构实现简易通讯录

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：无序数组取中位数
文章链接：http://soscw.com/index.php/essay/43440.html

亲，登录后才可以留言！

无序数组取中位数

评论

热门文章

推荐文章

最新文章

置顶文章