今天要给大家分享的是关于数据流中的中位数的相关内容，那么你知道怎样才能够得到一个数据流中的中位数吗?用代码如何实现呢?具体的思路又是怎样的?
怎样才能得到一个数据流中的中位数?
假如，从数据流中读出奇数个数值，则中位数就是所有数值排序之后位于中间的数值。
假如，从数据流中读出偶数个数值，则中位数就是所有数值排序之后中间两个数的平均值。
用Insert()方法读取数据流，用GetMedian()方法获取当前读取数据的中位数。
思路1：
构建一棵平衡二叉搜索树 。
每一个结点左子树都是小于等于其value的值，右子树都大于等于value值。
每一个子树都按照结点数调节平衡。
这样的话，根节点就一定是中间值中的一个。
假如，结点数是奇数，那么返回根节点的值。
假如，结点个数是偶数，那么，再从根结点左子数或者是右子数中个数较多的子树中选出最大或最小值就可以了。
代码实现：
struct myTreeNode
{
int val;
int count; //以此节点为根的树高
struct myTreeNode * left;
struct myTreeNode * right;
myTreeNode(int v):
val(v)
, count(1), left(NULL), right(NULL)
{}
};
myTreeNode * root = NULL;
class Solution
{
public:
/*计算以节点为根的树的高度
*/
int totalCount(myTreeNode * node)
{
if (node == NULL)
return 0;
else
return node - > count;
}
//左左
void rotateLL(myTreeNode * & t)
{
myTreeNode * k = t - > left;
myTreeNode * tm = NULL;
while (k - > right != NULL)
{
k - > count--;
tm = k;
k = k - > right;
}
if (k != t - > left)
{
k - > left = t - > left;
tm - > right = NULL;
}
t - > left = NULL;
k - > right = t;
t - > count = totalCount(t - > left) + totalCount(t - > right) + 1;
k - > count = totalCount(k - > left) + t - > count + 1;
t = k;
}
//右右
void rotateRR(myTreeNode * & t)
{
myTreeNode * k = t - > right;
myTreeNode * tm = NULL;
while (k - > left != NULL)
{
k - > count--;
tm = k;
k = k - > left;
}
if (k != t - > right)
{
k - > right = t - > right;
tm - > left = NULL;
}
t - > right = NULL;
k - > left = t;
t - > count = totalCount(t - > left) + 1;
k - > count = totalCount(k - > right) + t - > count + 1;
t = k;
}
//左右
void rotateLR(myTreeNode * & t)
{
rotateRR(t - > left);
rotateLL(t);
}
//右左
void rotateRL(myTreeNode * & t)
{
rotateLL(t - > right);
rotateRR(t);
}
//插入
void insert(myTreeNode * & root, int x)
{
if (root == NULL)
{
root = new myTreeNode(x);
return;
}
if (root - > val >= x)
{
insert(root - > left, x);
root - > count = totalCount(root - > left) + totalCount(root - > right) + 1;
if (2 == totalCount(root - > left) - totalCount(root - > right))
{
if (x < root - > left - > val)
{
rotateLL(root);
}
else
{
rotateLR(root);
}
}
}
else
{
insert(root - > right, x);
root - > count = totalCount(root - > left) + totalCount(root - > right) + 1;
if (2 == totalCount(root - > right) - totalCount(root - > left))
{
if (x > root - > right - > val)
{
rotateRR(root);
}
else
{
rotateRL(root);
}
}
}
}
void deleteTree(myTreeNode * root)
{
if (root == NULL) return;
deleteTree(root - > left);
deleteTree(root - > right);
delete root;
root = NULL;
}
void Insert(int num)
{
insert(root, num);
}
double GetMedian()
{
int lc = totalCount(root - > left), rc = totalCount(root - > right);
if (lc == rc)
return root - > val;
else
{
bool isLeft = lc > rc;
myTreeNode * tmp;
if (isLeft)
{
tmp = root - > left;
while (tmp - > right != NULL)
{
tmp = tmp - > right;
}
}
else
{
tmp = root - > right;
while (tmp - > left != NULL)
{
tmp = tmp - > left;
}
}
return (double)(root - > val + tmp - > val) / 2.0;
}
}
};以上的这种方式是思路比较清晰的，大家可以仔细的看一看。
思路2：
使用两个堆。
一个大顶堆和一个小顶堆来过滤数据。
自己实现的堆类。
代码实现：
public class Solution
{
private Heap maxHeap = new Heap(Heap.isMaxHeap);
private Heap minHeap = new Heap(Heap.isMinHeap);
/**
* 插入有两种思路：
* 1：直接插入大堆中，之后若两堆尺寸之差大于1(也就是2)，则从大堆中弹出堆顶元素并插入到小堆中
* 若两队之差不大于1，则直接插入大堆中即可。
* 2：奇数个数插入到大堆中，偶数个数插入到小堆中，
* 但是 可能会出现当前待插入的数比小堆堆顶元素大，此时需要将元素先插入到小堆，然后将小堆堆顶元素弹出并插入到大堆中
* 对于偶数时插入小堆的情况，一样的道理。why?
* 因为要保证最大堆的元素要比最小堆的元素都要小。
* @param num
*/
public void Insert(Integer num)
{
//若总尺寸为偶数，则插入大顶堆中
if (((maxHeap.si敏感词Heap.size()) & 1) == 0)
{
if (minHeap.size() != 0 && num > minHeap.peek())
{
minHeap.add(num);
maxHeap.add(minHeap.pop());
}
else
{
maxHeap.add(num);
}
}
else
{
if (maxHeap.size() != 0 && num < maxHeap.peek())
{
maxHeap.add(num);
minHeap.add(maxHeap.pop());
}
else
{
minHeap.add(num);
}
}
}
public Double GetMedian()
{
double res = 0.0;
if (((maxHeap.si敏感词Heap.size()) & 1) == 0)
{
res = (maxHeap.peek() + minHeap.peek()) / 2.0;
}
else
{
res = maxHeap.peek();
}
return res;
}
}
//堆类，可直接设置最大堆最小堆
class Heap
{
public List < Integer > list = null;
public static final boolean isMaxHeap = true;
public static final boolean isMinHeap = false;
private boolean flag = true; //true表示最大堆，false表示最小堆
public Heap()
{
this.list = new ArrayList < Integer > ();
}
public Heap(boolean flag)
{
this.list = new ArrayList < Integer > ();
this.flag = flag;
}
//获取堆大小
public int size()
{
return this.list.size();
}
//获取堆顶元素
public int peek()
{
if (list.size() == 0) return 0;
return list.get(0);
}
//插入元素，从插入点开始向上调整堆
public void add(int val)
{
this.list.add(val);
int i = list.size() - 1, index, parent, cur;
while (i > 0)
{
index = (i - 1) / 2;
parent = list.get(index);
cur = list.get(i);
if (flag == true && parent < cur)
{
swap(index, i);
}
else if (flag == false && parent > cur)
{
swap(index, i);
}
i = index;
}
}
/**
* 将堆顶元素取出,并重新调整堆。
* 1>取出堆顶元素
* 2>将最后一个元素放到堆顶
* 3>向下调整堆
*/
public int pop()
{
if (list.size() == 0) return -1;
int res = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
int len = list.size() - 1, i = 0;
int left, right;
while (i < len)
{
left = (i << 1) + 1;
right = (i << 1) + 2;
int maxIndex = i;
if (flag == true)
{
if (left < len && list.get(left) > list.get(maxIndex)) maxIndex = left;
if (right < len && list.get(right) > list.get(maxIndex)) maxIndex = right;
}
else
{
if (left < len && list.get(left) < list.get(maxIndex)) maxIndex = left;
if (right < len && list.get(right) < list.get(maxIndex)) maxIndex = right;
}
if (maxIndex != i)
{
swap(maxIndex, i);
i = maxIndex;
}
else break;
}
return res;
}
//交换list中两个位置的元素
public void swap(int i, int j)
{
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
}以上的这种思路也是可以的哦，大家也可以参照一下。
思路3：（最简单清晰）
import java.util.*;
// 运行时间：23ms
// 占用内存：9104k
public class Solution
{
ArrayList < Integer > res = new ArrayList < > ();
public void Insert(Integer num)
{
res.add(num);
Collections.sort(res);
}
public Double GetMedian()
{
int n = res.size();
if (n % 2 == 0)
{
return Double.valueOf((res.get(n / 2) + res.get(n / 2 - 1)) / 2.0);
}
else
{
return Double.valueOf(res.get(n / 2));
}
}
}好啦，以上三种关于怎样才能够得到一个数据流中的中位数思路大家都了解了吗？想了解更多的Java实例，可以继续的关注本站哦。