问题描述
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[2,3,4]，中位数是 3[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 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 以内的答案将被视作正确答案。
解题思路
方法一：双 multiset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<double> ans(n - k + 1);
multiset<int, greater<>> left;
multiset<int, less<>> right;
for (int i = 0; i < n; ++i) {
right.emplace(nums[i]);
left.emplace(*right.begin());
right.erase(right.begin());
if (left.size() + right.size() > k) {
auto it = right.find(nums[i - k]);
if (it != right.end()) right.erase(it);
else left.erase(left.find(nums[i - k]));
}
while (left.size() > right.size()) {
right.emplace(*left.begin());
left.erase(left.begin());
}
if (left.size() + right.size() == k) {
ans[i - k + 1] = k & 1 ? (double)*right.begin() : ((double)*right.begin() + *left.begin()) / 2;
}
}
return ans;
}
};
|
方法二：双 set
来自：Java using two Tree Sets - O(n logk)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
auto gt_cmp = [&nums] (int i, int j) {
return nums[i] != nums[j] ? nums[i] > nums[j] : i < j;
};
auto lt_cmp = [&nums] (int i, int j) {
return nums[i] != nums[j] ? nums[i] < nums[j] : i < j;
};
set<int, decltype(gt_cmp)> left(gt_cmp);
set<int, decltype(lt_cmp)> right(lt_cmp);
auto balance = [&left, &right] {
while (left.size() > right.size()) {
right.emplace(*left.begin());
left.erase(left.begin());
}
};
function<double()> median;
if (k & 1) {
median = [&nums, &right] {
return nums[*right.begin()];
};
} else {
median = [&nums, &left, &right] {
return ((double) nums[*right.begin()] + nums[*left.begin()]) / 2;
};
}
int n = nums.size();
vector<double> ans(n - k + 1);
for (int i = 0; i < k; ++i) left.emplace(i);
balance(); ans[0] = median();
for (int i = k; i < n; ++i) {
if (!right.erase(i - k)) left.erase(i - k);
right.emplace(i), left.emplace(*right.begin()), right.erase(right.begin());
balance(); ans[i - k + 1] = median();
}
return ans;
}
};
|
因为保存的元素是下标，不存在重复值，所以可以使用 set。
方法三：单 set 加中位数指针
来自：O(n log k) C++ using multiset and updating middle-iterator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
auto cmp = [&nums] (int i, int j) {
return nums[i] != nums[j] ? nums[i] < nums[j] : i < j;
};
set<int, decltype(cmp)> window(cmp);
for (int i = 0; i < k; ++i) window.emplace(i);
auto mid = next(window.begin(), k / 2);
int n = nums.size();
vector<double> ans(n - k + 1);
ans[0] = ((double) nums[*mid] + nums[*prev(mid, 1 - (k & 1))]) / 2;
for (int i = k; i < n; ++i) {
window.emplace(i);
if (nums[i] < nums[*mid]) --mid;
if (nums[i - k] <= nums[*mid]) ++mid;
window.erase(i - k);
ans[i - k + 1] = ((double) nums[*mid] + nums[*prev(mid, 1 - (k & 1))]) / 2;
}
return ans;
}
};
|
关于中位数指针的移动，可以对 \(k\) 为奇数和偶数时分别考虑，发现无论奇偶，下面的移动总是成立的。
| window.emplace(i);
if (nums[i] < nums[*mid]) --mid;
if (nums[i - k] <= nums[*mid]) ++mid;
window.erase(i - k);
|
而且对于插入，要先插入后移动；对于删除，要先移动后删除。
方法四：神奇的 Python 切片赋值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
n = len(nums)
window = []
ans = []
for i in range(n):
idx = bisect_left(window, nums[i])
window[idx:idx] = [nums[i]]
if len(window) > k:
idx = bisect_left(window, nums[i - k])
window[idx:idx+1] = []
if len(window) == k:
median = (window[k // 2] + window[(k - 1) // 2]) / 2
ans.append(median)
return ans
|
前三种方法的时间复杂度都是 \(\mathcal{O}(n\log k)\)，最后一种方法的时间复杂度实际上是 \(\mathcal{O}(nk)\)。