上海网站被查,wordpress首页文章内容,百度爱采购推广平台,绍兴建站服务解题思路#xff1a; 第一种方法#xff08;使用自定义的Heap类实现#xff09; /**为了保证两边数据量的平衡ulli两边数据一样时,加入左边/lili两边数据不一样时,加入右边/li/ul但是, 随便一个数能直接加入吗?ul 第一种方法使用自定义的Heap类实现 /**为了保证两边数据量的平衡ulli两边数据一样时,加入左边/lili两边数据不一样时,加入右边/li/ul但是, 随便一个数能直接加入吗?ulli加入左边前, 应该挑右边最小的加入/lili加入右边前, 应该挑左边最大的加入/li/ul*/题解
//设置左边履行的是大顶堆
private Heap left new Heap(10, false);
//设置右边履行的是小顶堆
private Heap right new Heap(10, true);/**为了保证两边数据量的平衡ulli两边数据一样时,加入左边/lili两边数据不一样时,加入右边/li/ul但是, 随便一个数能直接加入吗?ulli加入左边前, 应该挑右边最小的加入/lili加入右边前, 应该挑左边最大的加入/li/ul*/
public void addNum(int num) {if (left.size() right.size()) {right.offer(num);left.offer(right.poll());} else {left.offer(num);right.offer(left.poll());}
}/*** ul* li两边数据一致, 左右各取堆顶元素求平均/li* li左边多一个, 取左边元素/li* /ul*/
public double findMedian() {if (left.size() right.size()) {return (left.peek() right.peek()) / 2.0;} else {return left.peek();}
}
可以扩容的 heap, max 用于指定是大顶堆还是小顶堆
public class Heap {int[] array;int size;boolean max;public int size() {return size;}//当max为true则为大顶堆 如果是false则为小顶堆public Heap(int capacity, boolean max) {this.array new int[capacity];this.max max;}/*** 获取堆顶元素** return 堆顶元素*/public int peek() {return array[0];}/*** 删除堆顶元素** return 堆顶元素*/public int poll() {int top array[0];swap(0, size - 1);size--;down(0);return top;}/*** 删除指定索引处元素** param index 索引* return 被删除元素*/public int poll(int index) {int deleted array[index];swap(index, size - 1);size--;down(index);return deleted;}/*** 替换堆顶元素** param replaced 新元素*/public void replace(int replaced) {array[0] replaced;down(0);}/*** 堆的尾部添加元素** param offered 新元素*/public void offer(int offered) {if (size array.length) {grow();}up(offered);size;}//如果容量不够就进行扩容private void grow() {int capacity size (size 1);int[] newArray new int[capacity];//将原有的数组重新放到扩容好的数组中System.arraycopy(array, 0,newArray, 0, size);array newArray;}// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered) {int child size;while (child 0) {int parent (child - 1) / 2;boolean cmp max ? offered array[parent] : offered array[parent];if (cmp) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}public Heap(int[] array, boolean max) {this.array array;this.size array.length;this.max max;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点 size / 2 - 1for (int i size / 2 - 1; i 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left parent * 2 1;int right left 1;int min parent;if (left size (max ? array[left] array[min] : array[left] array[min])) {min left;}if (right size (max ? array[right] array[min] : array[right] array[min])) {min right;}if (min ! parent) { // 找到了更大的孩子swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}
} 本题还可以使用平衡二叉搜索树求解不过代码比两个堆复杂 第二种方法使用java现成的类实现 上面我们是使用的是自定义的heap类来进行实现的但是我们Java其实是有这么一个现成的类“PriorityQueue” 解题思路 /** * 为了保证两边数据量的平衡 * ul * li两边个数一样时,左边个数加一/li * li两边个数不一样时,右边个数加一/li * /ul * 但是, 随便一个数能直接加入吗? * ul * li左边个数加一时, 把新元素加在右边弹出右边最小的加入左边/li * li右边个数加一时, 把新元素加在左边弹出左边最小的加入右边/li * /ul */ 代码
public class E04Leetcode295_2 {/*** 为了保证两边数据量的平衡* ul* li两边个数一样时,左边个数加一/li* li两边个数不一样时,右边个数加一/li* /ul* 但是, 随便一个数能直接加入吗?* ul* li左边个数加一时, 把新元素加在右边弹出右边最小的加入左边/li* li右边个数加一时, 把新元素加在左边弹出左边最小的加入右边/li* /ul*/public void addNum(int num) {if (left.size() right.size()) {right.offer(num);left.offer(right.poll());} else {left.offer(num);right.offer(left.poll());}}/*** ul* li两边数据一致, 左右各取堆顶元素求平均/li* li左边多一个, 取左边堆顶元素/li* /ul*/public double findMedian() {if (left.size() right.size()) {return (left.peek() right.peek()) / 2.0;} else {return left.peek();}}// 大顶堆private PriorityQueueInteger left new PriorityQueue((a, b) - Integer.compare(b, a) //);// 小顶堆private PriorityQueueInteger right new PriorityQueue((a, b) - Integer.compare(a, b) //);public static void main(String[] args) {/*E04Leetcode295_2 test new E04Leetcode295_2();test.addNum(1);test.addNum(2);test.addNum(3);test.addNum(7);test.addNum(8);test.addNum(9);System.out.println(test.findMedian());test.addNum(10);System.out.println(test.findMedian());test.addNum(4);System.out.println(test.findMedian());*/// 以上浮为例, 大概的实现逻辑
// ComparatorInteger cmp (a, b) - Integer.compare(a, b); // 小顶堆比较器 compare -1 ab, 0 ab, 1 abComparatorInteger cmp (a, b) - Integer.compare(b, a); // 大顶堆比较器 compare -1 ba, 0 ba, 1 baint a 10; // 父元素值int b 20; // 新增元素值if (cmp.compare(a, b) 0) {System.out.println(上浮);} else {System.out.println(停止上浮);}}}
