leetcode_480. 滑动窗口中位数
目录
一、题目内容
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[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 以内的答案将被视作正确答案。
二、解题思路
1.暴力法：每次取k个数，排序后得到中位数；
2.二分插入排序和二分查找法，维护一个长度为k的滑动窗口，每次移动都需要进行二分插入排序算法插入右端的元素，然后利用二分查找将左端的数pop出去，然后得到中位数。可以利用bisect求解更快。
三、代码
-
class Solution:
-
def medianSlidingWindow(self, nums: list, k: int) -> list:
-
ans = []
-
for i in range(len(nums) - k + 1):
-
tmp = sorted(nums[i:i+k])
-
if k % 2 == 0:
-
center = (tmp[k // 2] + tmp[k // 2 - 1]) / 2
-
else:
-
center = tmp[k // 2]
-
ans.append(center)
-
-
return ans
-
-
def medianSlidingWindow1(self, nums, k: int):
-
-
def find_index_in_list(a, x, left=0, right=None):
-
if right is None:
-
right = len(a)
-
while left < right:
-
mid = (left + right) // 2
-
if a[mid] < x:
-
left = mid + 1
-
else:
-
right = mid
-
return left
-
-
def insert_x_in_list(a, x, left=0, right=None):
-
if right is None:
-
right = len(a)
-
while left < right:
-
mid = (left + right) // 2
-
if a[mid] < x:
-
left = mid + 1
-
else:
-
right = mid
-
a.append(0)
-
if len(a) == 1:
-
a[0] = x
-
else:
-
i = len(a) - 2
-
if i >= left:
-
a[left + 1:i + 2] = a[left:i + 1]
-
a[left] = x
-
-
ans = []
-
tmp = []
-
left, right = 0, k - 1
-
for right in range(len(nums)):
-
insert_x_in_list(tmp, nums[right])
-
while len(tmp) > k:
-
tmp.pop(find_index_in_list(tmp, nums[left]))
-
left += 1
-
if len(tmp) == k:
-
if k % 2 == 0:
-
ans.append((tmp[(k + 1) // 2 - 1] + tmp[(k + 1) // 2]) / 2)
-
else:
-
ans.append(tmp[(k + 1) // 2 - 1])
-
return ans
-
-
def medianSlidingWindow2(self, nums, k: int):
-
import bisect
-
ans = []
-
tmp = []
-
left, right = 0, k - 1
-
for right in range(len(nums)):
-
bisect.insort(tmp, nums[right]) # 利用二分查找算法来在有序序列中插入元素
-
while len(tmp) > k:
-
tmp.pop(bisect.bisect_left(tmp, nums[left])) # 利用二分查找算法来在有序序列中查找元素
-
left += 1
-
if len(tmp) == k:
-
if k % 2 == 0:
-
ans.append((tmp[(k + 1) // 2 - 1] + tmp[(k + 1) // 2]) / 2)
-
else:
-
ans.append(tmp[(k + 1) // 2 - 1])
-
return ans
-
-
-
if __name__ == '__main__':
-
s = Solution()
-
nums = [1, 3, -1, -3, 5, 3, 6, 7]
-
k = 3
-
ans = s.medianSlidingWindow1(nums, k)
-
print(ans)
文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。
原文链接：nickhuang1996.blog.csdn.net/article/details/113607012
- 点赞
- 收藏
- 关注作者
评论（0）