《剑指offer》刷题笔记。如有更好解法,欢迎留言。
关键字:堆
进制转化
队列
排序
题目描述:
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。
思路:
创建两个队列 left 和 right
1. 左右队列都为空时,将num随便放入左或者右。
2. 左队列为空,右队列不为空
- num 小于右队列队首,将 num 放入左队列。
- num 大于右队列队首,将右队列队首放到左队列,num 成为右队列新的队首。
3. 右队列为空,左队列不为空
- num 大于左队列队首,num 直接放入右队列。
- num 小于左队列队首,将左队列队首放入右队列,num 成为新的左队列队首。
4. 左右队列都不为空
- num 大于左队列队首,小于右队列队首,直接放入左队列队首。
- num 比两个队列的队首都小,把左队列队首放入右队列,把 num 放入左队列队首。
- num 比两个队列的队首都大,把右队列队首放入左队列,把 num 放入右队列。
- 不存在小于左队列队首但大于右队列队首的情况。
这时候,两个队列都基本有序了,但是还需要修正队首和队尾。
最后,将左右队列合并就能得到有序数据流。中位数按照奇偶情况获取。
- 完整代码
let left = [];
let right = [];
function Insert(num)
{
// 左右队列为空
if(left.length === 0 && right.length === 0){
left.push(num);
}
// 左队列为空,右队列不为空
else if(left.length === 0 && right.length !== 0){
if(num < right[0]){
left.push(num);
}else{
left.push(right.shift());
right.unshift(num);
}
}
// 右队列为空,左队列不为空
else if(left.length !== 0 && right.length === 0){
if(num > left[left.length-1]){
right.unshift(num);
}else{
right.unshift(left.pop());
left.push(num);
}
}
// 两个队列都不为空
else{
if(num > left[left.length-1] && num < right[0]){
left.push(num);
}else if(num < left[left.length-1] && num < right[0]){
right.unshift(left.pop());
left.push(num);
}else if(num > left[left.length-1] && num > right[0]){
left.push(right.shift());
right.unshift(num);
}
}
// 修正左右队列
if(left[0]>left[left.length-1]){
left.unshift(left.pop());
}
if(right[0]>right[right.length-1]){
right.push(right.shift());
}
}
function GetMedian(){
let temp = [...left,...right];
let l = temp.length;
if(l%2 === 0){
return (temp[Math.floor(l/2)]+temp[Math.floor(l/2)-1])/2;
}else{
return temp[Math.floor(l/2)];
}
}
网友评论