一個數據流中，隨時可以取得中位數。

題目描述：有一個源源不斷地吐出整數的數據流，假設你有足夠的空間來保存吐出的數。請設計一個名叫MedianHolder的結構，MedianHolder可以隨時取得之前吐出所有樹的中位數。

要求：

1.如果MedianHolder已經保存了吐出的N個數，那么任意時刻將一個新的數加入到MedianHolder的過程中，時間復雜度O(logN)。

2.取得已經吐出的N個數整體的中位數的過程，時間復雜度O(1).

看這要求就應該感覺到和堆相關吧？

但是進一步沒那么好想。

設計的MedianHolder中有兩個堆，一個是大根堆，一個是小根堆。大根堆中含有接收的所有數中較小的一半，并且按大根堆的方式組織起來，那么這個堆的堆頂就是較小一半的數中最大的那個。小根堆中含有接收的所有數中較大的一半，并且按小根堆的方式組織起來，那么這個堆的堆頂就是較大一半的數中最小的那個。

例如，如果已經吐出的數為6,1,3,0,9,8,7,2.

較小的一半為：0,1,2,3，那么3就是這一半的數組成的大根堆的堆頂

較大的一半為：6,7,8,9，那么6就是這一半的數組成的小根堆的堆頂

因為此時數的總個數為偶數，所以中位數就是兩個堆頂相加，再除以2.

如果此時新加入一個數10，那么這個數應該放進較大的一半里，所以此時較大的一半數為6,7,8,9,10，此時6依然是這一半的數組成的小根堆的堆頂，因為此時數的總個數為奇數，所以中位數應該是正好處在中間位置的數，而此時大根堆有4個數，小根堆有5個數，那么小根堆的堆頂6就是此時的中位數。

如果此時又新加入一個數11，那么這個數也應該放進較大的一半里，此時較大一半的數為：6,7,8,9,10,11.這個小根堆大小為6，而大根堆的大小為4，所以要進行如下調整：

1.如果大根堆的size比小根堆的size大2，那么從大根堆里將堆頂元素彈出，并放入小根堆里

2，如果小根堆的size比大根堆的size大2，那么從小根堆里將堆頂彈出，并放入大根堆里。

經過這樣的調整之后，大根堆和小根堆的size相同。

總結如下：

大根堆每時每刻都是較小的一半的數，堆頂為這一堆數的最大值
小根堆每時每刻都是較大的一半的數，堆頂為這一堆數的最小值
新加入的數根據與兩個堆堆頂的大小關系，選擇放進大根堆或者小根堆里（或者放進任意一個堆里）
當任何一個堆的size比另一個size大2時，進行如上調整的過程。

這樣隨時都可以知道已經吐出的所有數處于中間位置的兩個數是什么，取得中位數的操作時間復雜度為O(1)，同時根據堆的性質，向堆中加一個新的數，并且調整堆的代價為O（logN）。
?

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;/*** 隨時找到數據流的中位數* 思路：* 利用一個大根堆和一個小根堆去保存數據，保證前一半的數放在大根堆，后一半的數放在小根堆* 在添加數據的時候，不斷地調整兩個堆的大小，使得兩個堆保持平衡* 要取得的中位數就是兩個堆堆頂的元素*/
public class MedianQuick {public static class MedianHolder {private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());/*** 調整堆的大小* 當兩個堆的大小差值變大時，從數據多的堆中彈出一個數據進入另一個堆中*/private void modifyTwoHeapsSize() {if (this.maxHeap.size() == this.minHeap.size() + 2) {this.minHeap.add(this.maxHeap.poll());}if (this.minHeap.size() == this.maxHeap.size() + 2) {this.maxHeap.add(this.minHeap.poll());}}/*** 添加數據的過程** @param num*/public void addNumber(int num) {if (this.maxHeap.isEmpty()) {this.maxHeap.add(num);return;}if (this.maxHeap.peek() >= num) {this.maxHeap.add(num);} else {if (this.minHeap.isEmpty()) {this.minHeap.add(num);return;}if (this.minHeap.peek() > num) {this.maxHeap.add(num);} else {this.minHeap.add(num);}}modifyTwoHeapsSize();}/*** 獲取中位數** @return*/public Integer getMedian() {int maxHeapSize = this.maxHeap.size();int minHeapSize = this.minHeap.size();if (maxHeapSize + minHeapSize == 0) {return null;}Integer maxHeapHead = this.maxHeap.peek();Integer minHeapHead = this.minHeap.peek();if (((maxHeapSize + minHeapSize) & 1) == 0) {return (maxHeapHead + minHeapHead) / 2;}return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;}}/*** 大根堆比較器*/public static class MaxHeapComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {if (o2 > o1) {return 1;} else {return -1;}}}/*** 小根堆比較器*/public static class MinHeapComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {if (o2 < o1) {return 1;} else {return -1;}}}// for testpublic static int[] getRandomArray(int maxLen, int maxValue) {int[] res = new int[(int) (Math.random() * maxLen) + 1];for (int i = 0; i != res.length; i++) {res[i] = (int) (Math.random() * maxValue);}return res;}// for test, this method is ineffective but absolutely rightpublic static int getMedianOfArray(int[] arr) {int[] newArr = Arrays.copyOf(arr, arr.length);Arrays.sort(newArr);int mid = (newArr.length - 1) / 2;if ((newArr.length & 1) == 0) {return (newArr[mid] + newArr[mid + 1]) / 2;} else {return newArr[mid];}}public static void printArray(int[] arr) {for (int i = 0; i != arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {boolean err = false;int testTimes = 200000;for (int i = 0; i != testTimes; i++) {int len = 30;int maxValue = 1000;int[] arr = getRandomArray(len, maxValue);MedianHolder medianHold = new MedianHolder();for (int j = 0; j != arr.length; j++) {medianHold.addNumber(arr[j]);}if (medianHold.getMedian() != getMedianOfArray(arr)) {err = true;printArray(arr);break;}}System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");}
}

金條

一塊金條切成兩半，是需要花費和長度數值一樣的銅板的。比如長度為20的金條，不管切成長度多大的兩半，都要花費20個銅板。一群人想整分整塊金條，怎么分最省銅板？
例如，給定數組{10,20,30},代表一共三個人，整塊金條長度為10+20+30=60，金條要分成10,20,30三個部分。如果，先把長度60的金條分成10和50，花費60，再把長度為50的金條分成20和30，花費50，一共花費110個銅板。

但是如果，先把長度60的金條分成30和30，花費60，再把長度30金條分成10和30，花費30，一共花費90個銅板。

輸入一個數組，返回分割的最小代價。

首先我們要明白一點：不管合并策略是什么我們一共會合并n-1次，這個次數是不會變的。

我們要做的就是每一次都做最優選擇。

合為最優？

最小的兩個數合并就是最優。

所以

1）首先構造小根堆

2）每次取最小的兩個數（小根堆），使其代價最小。并將其和加入到小根堆中

3）重復（2）過程，直到最后堆中只剩下一個節點。

花費為每次花費的累加。

代碼略。