首页 > 代码库 > CC150 20.9
CC150 20.9
20.9 Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
class MedianNum { // O(n) void insert(int n) { if (size == 0) { head = new Node(n); media = head; } else if (n < head.num) { Node newHead = new Node(n); newHead.next = head; head.pre = newHead; head = newHead; median = median.pre; } else { // Find the position Node n = head; boolean passMedian = false; Node node = new Node(i); while (n.next != null) { if (n.next.num > n) { node.next = n.next; n.next.pre = node; n.next = node; node.pre = n; if (passMedian) { median = median.next; } else { median = median.pre; } break; } passMedian = n == median; } // At the end n.next = node; node.pre = n; median = median.pre; } size++; } // O(1) int medium() { if (size == 0) throw Exception; if (size % 2 == 1) // odd { return median.num; } else // Even { return ( median.num + median.next.nu ) / 2; } } private class Node { int num; Node next; Node.pre; } private Node head = null; private Node median = null; private int size = 0; } // What about using heap. class MedianNum { private size = 0; Heap minHeap; // All nums > median Heap maxHeap; // All nums <= median // O(log n) void insert(int n) { if(size == 0) { maxHeap.inseart(n); } else if (size == 1 && n >= maxHeap.top()) { minHeap.inseart(n); } else if (n <= maxHeap.top()) { minHeap.inseart(maxHeap.removeTop()); maxHeap.inseart(n); } else { maxHeap.inseart(minHeap.removeTop()); minHeap.inseart(n); } size++; } // O(1) in median() { if (size == 0) throw exception if (size % 2 == 1) { return maxHeap.top(); } else { return (maxHeap.top() + minHeap.top()) / 2; } } }
CC150 20.9
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。