In this Leetcode Sliding Window Median problem solution Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.
Problem solution in Python.
def medianSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[float]
"""
import bisect
left = []
right = []
result = []
for i, n in enumerate(nums):
if i + 1 > k:
pop_idx = i - k
if nums[pop_idx] <= left[-1]:
pos = bisect.bisect_left(left, nums[pop_idx])
left.pop(pos)
else:
pos = bisect.bisect_left(right, nums[pop_idx])
right.pop(pos)
if not left or n > left[-1]:
bisect.insort(right, n)
else:
bisect.insort(left, n)
while len(left) > len(right) + 1:
x = left.pop(-1)
bisect.insort(right, x)
while len(right) > len(left):
x = right.pop(0)
bisect.insort(left, x)
if i + 1 >= k:
if len(left) > len(right):
result.append(left[-1])
else:
result.append((left[-1] + right[0]) / 2.0)
return result
Problem solution in Java.
class Solution { public double[] medianSlidingWindow(int[] nums, int k) { int n = nums.length; double[] res = new double[n - k + 1]; int i = 0; //index of res int l = 0, r = k - 1; while (r < n) { int[] tmp = Arrays.copyOfRange(nums, l, r + 1); Arrays.sort(tmp); if (k % 2 == 1) { res[i++] = tmp[k / 2] * 1.0; } else { res[i++] = (tmp[k / 2 - 1] * 1.0 + tmp[k / 2] * 1.0) / 2; } l++; r++; } return res; } }
Problem solution in C++.
class Solution { public: vector<double> medianSlidingWindow(vector<int>& nums, int k) { multiset<int> ms; for (int i = 0; i < k - 1; ++i) ms.insert(nums[i]); vector<double> res; for (int i = k - 1; i < nums.size(); ++i) { ms.insert(nums[i]); auto it = next(ms.begin(), (k - 1) / 2); res.push_back(k % 2 ? *it : ((static_cast<double>(*it) + *next(it)) / 2)); ms.erase(ms.lower_bound(nums[i - k + 1])); } return res; } };
0 Comments