数据流中的中位数

《剑指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)];
  }
}