题解

该题聚焦点为如何高效的对移动窗口内数据进行排序，当窗口已经有序的时候，向右移动一格，需要把新加入的数据替换掉该剔除的数据，此时就变成一个有序数组里有一个数是乱序的，此时只要将这一个乱序数进行插入排序即可。总的时间复杂度为 n*O(n)

代码

  1. var medianSlidingWindow = function(nums, k) {
  2.     // 记录结果
  3.     let ret = []
  4.     // 窗口数组
  5.     let arr = nums.slice(0, k)
  6.     // 首次进行快排
  7.     quickSort(arr)
  8.     // 放入第一个中位数
  9.     ret.push(calcMid(arr))
  10.     // 遍历原数组
  11.     for (let i = 1; i <= nums.length - k; i++) {
  12.         binarySearchSort(arr, nums[i-1], nums[i-1+k])
  13.         ret.push(calcMid(arr))
  14.     }
  15.     return ret
  16. };
  18. function calcMid(arr) {
  19.     let sum = arr.length - 1
  20.     if (sum % 2 === 0) {
  21.         return arr[sum/2]
  22.     } else {
  23.         let mid = Math.floor(sum/2)
  24.         return (arr[mid] + arr[mid + 1]) / 2
  25.     }
  26. }
  28. function quickSort(arr) {
  29.     arr.sort((a, b) => a - b)
  30. }
  32. function binarySearchSort(arr, remove, add) {
  33.     // 使用 add 替换 remove 并返回 remove 所在位置
  34.     let index = binarySearchReplace(arr, remove, add)
  35.     // 重新排序，从 index 位置进行一次插入排序
  36.     insertSortFromIndex(arr, index)
  37. }
  39. function insertSortFromIndex(arr, index) {
  40.     let flag = false
  41.     while (index >= 1 && arr[index - 1] > arr[index]) {
  42.         [arr[index - 1], arr[index]] = [arr[index], arr[index - 1]]
  43.         index--
  44.         flag = true
  45.     }
  46.     if (flag) return
  47.     while (index < arr.length - 1 && arr[index + 1] < arr[index]) {
  48.         [arr[index + 1], arr[index]] = [arr[index], arr[index + 1]]
  49.         index++
  50.     }
  51. }
  53. function binarySearchReplace(arr, remove, add) {
  54.     let index = binarySearch(arr, remove, 0, arr.length - 1)
  55.     arr[index] = add
  56.     return index
  57. }
  59. function binarySearch(arr, target, start, end) {
  60.     if (start <= end) {
  61.         let mid = Math.floor((start + end) / 2)
  62.         if (arr[mid] === target) {
  63.             return mid
  64.         } else if (arr[mid] < target) {
  65.             start = mid + 1
  66.             return binarySearch(arr, target, start, end)
  67.         } else {
  68.             end = mid - 1
  69.             return binarySearch(arr, target, start, end)
  70.         }
  71.     } else {
  72.         return -1
  73.     }
  74. }