题目大意：让你求移动窗口的中位数。
Problem:
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples:
[2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
|
1 2 3 4 5 6 7 8 |
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 |
Therefore, return the median sliding window as [1,-1,-1,3,5,6].
Note:
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.
Solution 0: Brute Force
Time complexity: O(n*klogk) TLE 32/42 test cases passed
Solution 1: Insertion Sort
Time complexity: O(k*logk + (n – k + 1)*k)
Space complexity: O(k)
C++ / vector
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 99 ms class Solution { public: vector<double> medianSlidingWindow(vector<int>& nums, int k) { vector<double> ans; if (k == 0) return ans; vector<int> window(nums.begin(), nums.begin() + k - 1); std::sort(window.begin(), window.end()); for (int i = k - 1; i < nums.size(); ++i) { window.push_back(nums[i]); auto it = prev(window.end(), 1); auto const insertion_point = std::upper_bound(window.begin(), it, *it); std::rotate(insertion_point, it, it + 1); ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2); window.erase(std::find(window.begin(), window.end(), nums[i - k + 1])); } return ans; } }; |
C++ / vector + binary_search for deletion.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 84 ms class Solution { public: vector<double> medianSlidingWindow(vector<int>& nums, int k) { vector<double> ans; if (k == 0) return ans; vector<int> window(nums.begin(), nums.begin() + k - 1); std::sort(window.begin(), window.end()); for (int i = k - 1; i < nums.size(); ++i) { window.push_back(nums[i]); auto it = prev(window.end(), 1); auto const insertion_point = std::upper_bound(window.begin(), it, *it); std::rotate(insertion_point, it, it + 1); ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2); window.erase(std::lower_bound(window.begin(), window.end(), nums[i - k + 1])); } return ans; } }; |
Java
|
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 |
// Author: Huahua // Running time: 60 ms class Solution { public double[] medianSlidingWindow(int[] nums, int k) { if (k == 0) return new double[0]; double[] ans = new double[nums.length - k + 1]; int[] window = new int[k]; for (int i = 0; i < k; ++i) window[i] = nums[i]; Arrays.sort(window); for (int i = k; i <= nums.length; ++i) { ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2; if (i == nums.length) break; remove(window, nums[i - k]); insert(window, nums[i]); } return ans; } // Insert val into window, window[k - 1] is empty before inseration private void insert(int[] window, int val) { int i = 0; while (i < window.length - 1 && val > window[i]) ++i; int j = window.length - 1; while (j > i) window[j] = window[--j]; window[j] = val; } // Remove val from window and shrink it. private void remove(int[] window, int val) { int i = 0; while (i < window.length && val != window[i]) ++i; while (i < window.length - 1) window[i] = window[++i]; } } |
Java / Binary Search
|
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 |
// Author: Huahua // Running time: 47 ms (<98.96%) class Solution { public double[] medianSlidingWindow(int[] nums, int k) { if (k == 0) return new double[0]; double[] ans = new double[nums.length - k + 1]; int[] window = new int[k]; for (int i = 0; i < k; ++i) window[i] = nums[i]; Arrays.sort(window); for (int i = k; i <= nums.length; ++i) { ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2; if (i == nums.length) break; remove(window, nums[i - k]); insert(window, nums[i]); } return ans; } // Insert val into window, window[k - 1] is empty before inseration private void insert(int[] window, int val) { int i = Arrays.binarySearch(window, val); if (i < 0) i = - i - 1; int j = window.length - 1; while (j > i) window[j] = window[--j]; window[j] = val; } // Remove val from window and shrink it. private void remove(int[] window, int val) { int i = Arrays.binarySearch(window, val); while (i < window.length - 1) window[i] = window[++i]; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
""" Author: Huahua Running time: 161 ms (< 93.75%) """ class Solution: def medianSlidingWindow(self, nums, k): if k == 0: return [] ans = [] window = sorted(nums[0:k]) for i in range(k, len(nums) + 1): ans.append((window[k // 2] + window[(k - 1) // 2]) / 2.0) if i == len(nums): break index = bisect.bisect_left(window, nums[i - k]) window.pop(index) bisect.insort_left(window, nums[i]) return ans |
Solution 2: BST
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 68 ms class Solution { public: vector<double> medianSlidingWindow(vector<int>& nums, int k) { vector<double> ans; if (k == 0) return ans; multiset<int> window(nums.begin(), nums.begin() + k); auto mid = next(window.begin(), (k - 1) / 2); for (int i = k; i <= nums.size(); ++i) { ans.push_back((static_cast<double>(*mid) + *next(mid, (k + 1) % 2)) / 2.0); if (i == nums.size()) break; window.insert(nums[i]); if (nums[i] < *mid) --mid; if (nums[i - k] <= *mid) ++mid; window.erase(window.lower_bound(nums[i - k])); } return ans; } }; |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment