在哪个网站上做简历,网站设计师网站,WordPress资源路径,石家庄广告公司前十名一个数据流中#xff0c;随时可以取得中位数。 题目描述#xff1a;有一个源源不断地吐出整数的数据流#xff0c;假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构#xff0c;MedianHolder可以随时取得之前吐出所有树的中位数。
要求#xff1a;
1…一个数据流中随时可以取得中位数。 题目描述有一个源源不断地吐出整数的数据流假设你有足够的空间来保存吐出的数。请设计一个名叫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)同时根据堆的性质向堆中加一个新的数并且调整堆的代价为OlogN。
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;/*** 随时找到数据流的中位数* 思路* 利用一个大根堆和一个小根堆去保存数据保证前一半的数放在大根堆后一半的数放在小根堆* 在添加数据的时候不断地调整两个堆的大小使得两个堆保持平衡* 要取得的中位数就是两个堆堆顶的元素*/
public class MedianQuick {public static class MedianHolder {private PriorityQueueInteger maxHeap new PriorityQueueInteger(new MaxHeapComparator());private PriorityQueueInteger minHeap new PriorityQueueInteger(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 ComparatorInteger {Overridepublic int compare(Integer o1, Integer o2) {if (o2 o1) {return 1;} else {return -1;}}}/*** 小根堆比较器*/public static class MinHeapComparator implements ComparatorInteger {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},代表一共三个人整块金条长度为10203060金条要分成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过程直到最后堆中只剩下一个节点。 花费为每次花费的累加。
代码略。 项目最大收益贪心问题 输入参数1正数数组costs参数2正数数组profits参数3正数k参数4正数m
costs[i]表示i号项目的花费profits[i]表示i号项目在扣除花费之后还能挣到的钱利润,k表示你不能并行只能串行的最多做k个项目m表示你初始的资金。
说明你每做完一个项目马上获得的收益可以支持你去做下一个项目。
输出你最后获得的最大钱数。
思考给定一个初始化投资资金给定N个项目想要获得其中最大的收益并且一次只能做一个项目。这是一个贪心策略的问题应该在能做的项目中选择收益最大的。
按照花费的多少放到一个小根堆里面然后要是小根堆里面的头节点的花费少于给定资金就将头节点一个个取出来放到按照收益的大根堆里面。然后做大根堆顶的项目即可。
