#480
Sliding Window Median
master · 1735 · lc hard +32 · verified · 38.9% accepted · 3,568 likes · top 18%
Description
The median of a sorted sequence is its middle value; for even-length sequences it is the average of the two central values (e.g., the median of [1,2,3,4] is 2.5).
A window of size k shifts one position at a time from left to right across integer array nums. After each shift, record the median of the k elements currently in the window.
Return the resulting list of medians. Answers within 10-5 of the true value are accepted.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:
Window position Median
--------------- -----
[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
Example 2:
Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
Code
1
2
3