各位题友大家好，今天是每日算法题公众号坚持日更的第 10 天。今天力扣上的每日一题是第 480 题「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] 。

数据范围

题目未给出。

解题思路

2 月份已经连续三天都是滑动窗口了。上个月是并查集月，这个月看来是滑动窗口月了。

今天题目的意思很简单，要求滑动窗口中的元素的中位数。如果是求平均数，就简单很多了：每次滑动窗口移动，都是增加一个元素、删除一个元素，因此窗口内元素的 和 是非常好维护的，再除以窗口的大小就能得到平均数。

中位数是有序序列最中间的那个数。也就是说我们必须对窗口内的元素「排序」。我们知道排序的时间复杂度一般是 O(k * log(k)) ，还是比较高的。这个题如果对每个区间都进行分别排序肯定会超时，否则也不会是个 Hard 题目。

怎么快速求中位数呢？为了降低时间复杂度的一个绝招就是增加空间复杂度：利用更好的数据结构。是的，我们的目的是快速让一组数据有序，那就寻找一个内部是有序的数据结构呗！下面我分语言讲解一下常见的内部有序的数据结构。

  1. 在 C++ 中 set/multiset 是有序的集合，它们是基于红黑树实现的。其中 set 会对元素去重，而 multiset 可以有重复元素。
    2. 在 Java 中 TreeSet 是有序的集合，它也是基于红黑树实现的。 TreeSet 会对元素去重。

  2. 在 Python 中 heapq 实现了堆的算法，它不会对元素去重。

当频繁的插入和删除元素时，这些有序的数据结构能够在在 O(log(k)) 的时间复杂度内维护结构的有序性。但是对于红黑树实现的数据结构来说，不能做随机读取，因此获取中位数的时候，也只能通过 O(k) 时间复杂度的查找。

代码

有了非常高效的数据结构，做这个题已经不难了。我下面的代码演示了用 C++ 的 multiset 解决本题。代码不长，但是需要对 C++ 的 stl 有一些了解。

  1. 首先定义了结果数组 res 和 multiset；
    2. 遍历输入中的每个元素；
    3. 如果 multiset 中的元素超过了 k 个，需要把滑动窗口最左边 i - k 位置元素从 multiset 中删除（multiset自动维护有序性）；
    4. 把遍历到的当前元素插入到 multiset 中（multiset自动维护有序性）；
    5. 如果当前的位置达到了下标 k - 1，说明滑动窗口中有 k 个元素，开始求滑动窗口的中位数。

我们知道，如果数组 A 长度 k 是奇数时，令 mid = k / 2 ，那么中位数元素是 A[mid] ；如果数组长度 k 为偶数时，那么中位数是 (A[mid] + A[mid - 1]) / 2 。为了适应奇数和偶数长度，可以用通用的表达式 (A[mid] + A[mid - (1 - k % 2)]) / 2来求中位数。

求 multiset 里的中位数：我们先求 multiset 中所有元素的起始位置（最小元素），然后在此基础上让指针走 k / 2 步得到 mid ，最终 (A[mid] + A[mid - (1 - k % 2)]) / 2 就是我们要求的中位数。

使用 C++ 写的代码如下。

  1. class Solution {
  2. public:
  3.     vector<double> medianSlidingWindow(vector<int>& nums, int k) {
  4.         vector<double> res;
  5.         multiset<double> st;
  6.         for (int i = 0; i < nums.size(); ++i) {
  7.             if (st.size() >= k) st.erase(st.find(nums[i - k]));
  8.             st.insert(nums[i]);
  9.             if (i >= k - 1) {
  10.                 auto mid = st.begin();
  11.                 std::advance(mid, k / 2);
  12.                 res.push_back((*mid + *prev(mid, (1 - k % 2))) / 2);
  13.             }
  14.         }
  15.         return res;
  16.     }
  17. };

时间复杂度： O(N*(log(k) + k)) ， log(k) 每次插入和删除操作， k 是找中位数操作。

刷题心得

本题最大的难点就在于怎么求频繁变化的数组中的中位数，为了不每次都排序，于是使用了内部就对元素进行排序的数据结构。程序 = 数据结构 + 算法，解决一个问题时，合适的数据结构和算法都很重要。

欢迎加入刷题群

目前已经近 2000 人加入了每日一题打卡群。加入方式是通过每日一题打卡网站。每天都会同步力扣每日一题，这是个互相帮助、互相监督的算法题打卡网站，其地址是 https://www.ojeveryday.com/
【每日一题】480. 滑动窗口中位数 - 图1

想加入千人刷题群的朋友，可以复制上面的链接到浏览器，然后在左侧点击「加入组织」，提交力扣个人主页，即可进入刷题群。期待你早日加入。

也可点击 「阅读原文」，直接提交力扣个人主页。

关于作者

我是本文的作者是负雪明烛，毕业于北京邮电大学，目前就职于阿里巴巴。坚持刷算法题 5 年，共计刷了 800 多道算法题。做过的每个算法题都在 CSDN 上写题解博客，获得好评无数，CSDN 的累计阅读量已经 160万 次！博客地址是：https://blog.csdn.net/fuxuemingzhu
「每日算法题」公众号是我维护的一个算法题解公众号，主要讲解算法题的解法，也会分享找工作的经验。欢迎关注。
【每日一题】480. 滑动窗口中位数 - 图2

题目来源：480. 滑动窗口中位数
链接：https://leetcode-cn.com/problems/sliding-window-median