480. 滑动窗口中位数

题目

中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

例

给出  nums = [1,3,-1,-3,5,3,6,7]，以及  k = 3。

窗口位置                      中位数
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7      -1
 1  3 [-1  -3  5] 3  6  7      -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

因此，返回该滑动窗口的中位数数组  [1,-1,-1,3,5,6]。

• 你可以假设 k 始终有效，即：k 始终小于输入的非空数组的元素个数。
• 与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。

题解

双优先队列 + 延迟刪除

见 leetcode

插入排序

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var medianSlidingWindow = function(nums, k) {
  // 初始化 滑动窗口
  let sliderWindow = nums.slice(0, k).sort((a, b) => a - b);

  let res = [];
  for (let i = 0; i <= nums.length - k; ++i) {
    // res 长度为 0 代表初始化状态
    if (res.length) {
      // 查询需要移除的位置，移除元素
      let out = sliderWindow.indexOf(nums[i - 1]);
      sliderWindow.splice(out, 1);

      // 需要加入的元素
      const newValue = nums[i + k - 1];

      // 队空直接加入
      if (!sliderWindow.length) {
        sliderWindow.push(newValue);
      }
      // 小于等于最小直接头插
      else if (newValue <= sliderWindow[0]) {
        sliderWindow.unshift(newValue);
      }
      // 大于等于最大直接尾插
      else if (newValue >= sliderWindow[sliderWindow.length - 1]) {
        sliderWindow.push(newValue);
      } else {
        // 中间插入排序
        for (let j = 0; j < sliderWindow.length - 1; ++j) {
          if (newValue >= sliderWindow[j] && newValue <= sliderWindow[j + 1]) {
            sliderWindow = [
              ...sliderWindow.slice(0, j + 1),
              newValue,
              ...sliderWindow.slice(j + 1)
            ];
            break;
          }
        }
      }
    }
    if (k % 2) {
      // 奇数
      res.push(sliderWindow[Math.floor(k / 2)]);
    } else {
      // 偶数
      res.push((sliderWindow[k / 2] + sliderWindow[k / 2 - 1]) / 2);
    }
  }
  return res;
};

优化：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var find = function(arr, value) {
  var left = 0,
    right = arr.length;
  while (left < right) {
    var mid = (right + left) >> 1;
    if (arr[mid] > value) {
      right = mid - 1;
    } else if (arr[mid] < value) {
      left = mid + 1;
    } else {
      return mid;
    }
  }
  return left;
};
var medianFun = function(k) {
  var isEven = k % 2 === 0;
  var half = k >> 1;
  return arr => {
    if (isEven) {
      return (arr[half] + arr[half - 1]) / 2;
    } else {
      return arr[half];
    }
  };
};
var medianSlidingWindow = function(nums, k) {
  var ans = [];
  var median = medianFun(k);
  // 有序数组arr
  var arr = nums.slice(0, k).sort((a, b) => a - b);
  ans.push(median(arr, 0, k));
  for (var i = k; i < nums.length; i++) {
    //删除第一个元素
    var removeIndex = find(arr, nums[i - k]);
    arr.splice(removeIndex, 1);
    //把当前元素加入到arr里
    var value = nums[i];
    var addIndex = find(arr, value);
    if (arr[addIndex] < value) addIndex++;
    arr.splice(addIndex, 0, value);
    ans.push(median(arr, 0, k));
  }
  return ans;
};