LeetCode 其他题目集

这里记录一些 LeetCode 上不是很难但可能会有所帮助的题目。

LeetCode 0480 - 滑动窗口中位数

题目描述

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

解题思路

方法一：使用搜索二叉树

无非就是用一个搜索二叉树，这样删除和插入都是 \(O(logn)\)，但是有个问题是需要找二叉树的中位数，所以每次都要遍历找。那就维护一个中位数指针吧。

for (int i = k; i < n; ++i) {
    st.insert(nums[i]);
    if (nums[i] < *mid) --mid;
    if (nums[i - k] <= *mid) ++mid;
    st.erase(st.lower_bound(nums[i - k]));
}

方法二：使用双堆

也有用两个堆来做的，这个就比较巧妙点。一个大顶堆一个小顶堆，小于中位数的在大顶堆，大于的在小顶堆。中位数就是两堆顶的平均（偶数情况）。

每次操作步骤：
1. 先删除旧的数，先和中位数比较，找到对应堆删除即可
2. 然后添加新来的数，也要和中位数比较
3. 根据情况来调整大顶堆或者小顶堆即可

Comments