第62题：二叉搜索树的第k个节点
难易度：⭐⭐
题目描述:
给定一棵二叉搜索树，请找出其中的第k小的结点。
例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
解析：
二叉搜索树的特点就是如果中序遍历二叉搜索树，打印出来的节点value值会按照从小到大的顺序进行排列，可以利用这一点，用一个变量去标记index值，当index等于k时，返回该节点即可。
代码如下:
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.Stack;
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k){
if(pRoot == null || k < 0){
return null;
}
int index = 0;
Stack<TreeNode> stack = new Stack<>();
while(pRoot != null || !stack.isEmpty()){
if(pRoot != null){
stack.push(pRoot);
pRoot = pRoot.left;
}else{
pRoot = stack.pop();
index++;
// do sth
if(index == k){
return pRoot;
}
pRoot = pRoot.right;
}
}
return null;
}
}
第63题：数据流中的中位数
难易度：⭐⭐⭐
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
如果你用一个数组去接收流吐出的数字，那么收集流吐出的数字很简单，但是如果要获取中位数的话就要对数组进行一次排序，如果要求流每次吐出一个数字就获取一次中位数，那么就要频繁地对数组进行排序操作。解决的方法就是使用堆结构来解决这个问题：设计一个最大堆，和一个最小堆，每次流吐出数字的时候都和最大堆的堆顶作比较，如果小于等于最大堆堆顶就放入最大堆，如果大于最大堆的堆顶则放入最小堆。同时我们还需要保证最大堆的数据量不能比最小堆中的数据量大超过1，反之亦是如此,也就是要保持最大堆数据量N和最小堆的数据量M的关系为 |N-M| <= 1,如何保持这种关系呢？一旦破坏了这种关系的平衡，我们就让最大堆的顶部或者最小堆的顶部弹出，让这个最大的数字进入到最小堆里面，或者是让最小堆的最小的数字加到最大堆里面，如图示意：
image.png
假设这个数据流吐出的数字依次是 5->6->4->7->3->8->1
左侧为最大堆数字数量为N，右侧为最小堆数字数量为M,没有破坏过 |N-M| <= 1的规定，如果这个时候数据流吐出的数字为0，那么就要add到最大堆里面，这个时候N-M = 2破坏了两堆数量上的平衡，所以要把最大堆的堆顶弹入到最小堆中去，操作如下：
首先将数字0 add 到最大堆中
image.png
交换最大堆首尾数字
image.png
将最大堆末尾数字(5) add 到最小堆
image.png
接下来就是heapify操作了，对最大堆中的堆顶0进行heapify,首先要判断它的两个孩子谁更大，谁大跟谁交换，直到满足最大堆的结构为止
image.png
本题的思路就是使用一个最大堆和一个最小堆解决，优先级队列PriorityQueue即可以满足本题的求解，代码如下:
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new MinHeapCompare());
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxHeapCompare());
public static class MinHeapCompare implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
public static class MaxHeapCompare implements Comparator<Integer>{
@Override
public int compare(Integer o1,Integer o2){
return o2 - o1;
}
}
private void modify(){
if(maxHeap.size() == minHeap.size() + 2){
minHeap.add(maxHeap.poll());
}
if(minHeap.size() == maxHeap.size() + 2){
maxHeap.add(minHeap.poll());
}
}
public void Insert(Integer num) {
if(maxHeap.isEmpty()){
maxHeap.add(num);
return;
}
if(num <= maxHeap.peek()){
maxHeap.add(num);
}else{
if(minHeap.isEmpty()){
minHeap.add(num);
return;
}
if(num < minHeap.peek()){
maxHeap.add(num);
}else{
minHeap.add(num);
}
}
modify();
}
public Double GetMedian() {
if(maxHeap.isEmpty() && minHeap.isEmpty()){
return null;
}
int maxHeapSize = maxHeap.size();
int minHeapSize = minHeap.size();
int maxHeapHead = maxHeapSize == 0 ? 0 : maxHeap.peek();
int minHeapHead = minHeapSize == 0 ? 0 :minHeap.peek();
if(maxHeapSize == minHeapSize){
return ((double)(maxHeapHead + minHeapHead))/2;
}
return maxHeapSize > minHeapSize ? (double)maxHeapHead : (double)minHeapHead;
}
}
网友评论