387. Window Middles
A fitness app logs the number of steps a user walks each day in the array nums. To smooth out freak days, it reports the typical value of every run of k consecutive days, where the typical value is the middle one after the days in that run are sorted by size.
If k is odd, the middle is the single center value. If k is even, the middle is the average of the two center values. Slide the run one day at a time and return an array with the middle of every run, in order. Answers within 10^-6 of the exact value are accepted.
Example 1
- Input:
- nums = [3,8,1,6,2], k = 3
- Output:
- [3,6,2]
- Explanation:
The runs are [3,8,1], [8,1,6] and [1,6,2]. Sorted they are [1,3,8], [1,6,8] and [1,2,6], so the middles are 3, 6 and 2.
Example 2
- Input:
- nums = [4,10,2,6], k = 2
- Output:
- [7,6,4]
- Explanation:
With an even k the middle is an average: (4+10)/2 = 7, (10+2)/2 = 6 and (2+6)/2 = 4.
Example 3
- Input:
- nums = [-5], k = 1
- Output:
- [-5]
- Explanation:
A single day is its own middle, so the answer is [-5].
Constraints
1 ≤ nums.length ≤ 4 * 105
-109 ≤ nums[i] ≤ 109
1 ≤ k ≤ nums.length
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)