首页 > 代码库 > 18.9 随机生成一些数字并传入某个插入方法。 编写一个程序，高效地插入过的元素的维护中位数。
18.9 随机生成一些数字并传入某个插入方法。 编写一个程序，高效地插入过的元素的维护中位数。
按照题意，要实现两个方法： addNewNumer(int num) 和 getMedian()
维护两个priority queue：maxHeap 和 minHeap。
maxHeap中存放小于中位数的元素，minHeap中存放大于中位数的元素。并且保证两个堆里元素数量相等或者max比min多一个。
import java.util.Comparator;import java.util.PriorityQueue;public class Median { PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10, new Comparator<Integer>() { public int compare(Integer x, Integer y) { return y.compareTo(x); } }); PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); public void addNewNumber(int num) { if (maxHeap.size() == minHeap.size()) { if (!minHeap.isEmpty() && num > minHeap.peek()) { maxHeap.add(minHeap.remove()); minHeap.add(num); } else { maxHeap.add(num); } } else { if (num < maxHeap.peek()) { minHeap.add(maxHeap.remove()); maxHeap.add(num); } else { minHeap.offer(num); } } } public double getMedian() { if (maxHeap.isEmpty()) return 0; if (maxHeap.size() == minHeap.size()) return (double) (minHeap.peek() + maxHeap.peek()) / 2; else return maxHeap.peek(); } public static void main(String[] args) { Median m = new Median(); m.addNewNumber(1); System.out.println(m.getMedian()); m.addNewNumber(3); System.out.println(m.getMedian()); m.addNewNumber(4); System.out.println(m.getMedian()); m.addNewNumber(5); System.out.println(m.getMedian()); m.addNewNumber(2); System.out.println(m.getMedian()); }}
18.9 随机生成一些数字并传入某个插入方法。 编写一个程序，高效地插入过的元素的维护中位数。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。