LeetCode 480题 “Sliding Window Median” 是一个中等难度的题目，要求我们在一个滑动窗口中找到中位数。中位数是指在一个有序数组中位于中间位置的数，如果数组长度是奇数，则中位数是中间那个数；如果数组长度是偶数，则中位数是中间两个数的平均值。
题目描述
给定一个数组 nums 和一个整数 k，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口的中位数数组。
示例
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [1,-1,-1,3,5,6]
解释:
滑动窗口的位置 中位数
[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
解题思路
要解决这个问题，我们可以使用两个数据结构：一个大顶堆（max heap）和一个小顶堆（min heap）。大顶堆用来存储窗口中较小的那一半元素，小顶堆用来存储较大的那一半元素。这样，我们可以保证：
- 大顶堆中的所有元素都小于等于小顶堆中的所有元素。
- 两个堆的大小之差不超过1。
通过这种方式，我们可以快速找到中位数：
- 如果两个堆的大小相等，中位数是两个堆顶元素的平均值。
- 如果两个堆的大小不相等，中位数是较大的那个堆的堆顶元素。
具体步骤
- 初始化：创建一个大顶堆
left 和一个小顶堆 right。
- 填充初始窗口：将前
k 个元素加入堆中，调整堆使其满足上述条件。
- 滑动窗口：从第
k 个元素开始，每次移动窗口时：
- 移除窗口最左边的元素。
- 添加窗口最右边的元素。
- 调整堆使其满足上述条件。
- 计算当前窗口的中位数并记录。
代码实现
以下是使用Python实现的代码：
import heapq
def medianSlidingWindow(nums, k):
def add_num(num):
if not left or num <= -left[0]:
heapq.heappush(left, -num)
else:
heapq.heappush(right, num)
balance()
def remove_num(num):
if num <= -left[0]:
left.remove(-num)
heapq.heapify(left)
else:
right.remove(num)
heapq.heapify(right)
balance()
def balance():
if len(left) > len(right) + 1:
heapq.heappush(right, -heapq.heappop(left))
if len(right) > len(left):
heapq.heappush(left, -heapq.heappop(right))
def get_median():
if len(left) == len(right):
return (-left[0] + right[0]) / 2
else:
return -left[0]
left, right = [], []
result = []
for i in range(len(nums)):
add_num(nums[i])
if i >= k:
remove_num(nums[i - k])
if i >= k - 1:
result.append(get_median())
return result
示例
nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(medianSlidingWindow(nums, k)) # 输出: [1, -1, -1, 3, 5, 6]
解释
- add_num(num)：将一个数加入堆中，并根据需要调整堆。
- remove_num(num)：从堆中移除一个数，并重新调整堆。
- balance()：确保两个堆的大小之差不超过1。
- get_median()：根据两个堆的顶元素计算中位数。
通过这种方式，我们可以在每个窗口移动时高效地计算中位数，从而解决这道题目。