在给定大小 K 和长度 N 的数组的情况下查找中位数最小的子数组

Question

在过去的一个月里，我一直在努力解决我们在解决课程中遇到的这个问题。任务是在整数数组中找到中位数最小且大小为 K 的窗口。还值得注意的是，K 总是奇数，因此我们不必担心偶数长度序列。

一个例子是： [1,3,3,2,1]，K = 3 我们有 [1,3,3], [3,3,2], [3,2,1] 排序后得到 [1,3,3], [2,3,3], [1,2 ,3] 因此我们的答案是 2.

我已经实现了一种使用滑动窗口技术然后对每个窗口进行排序的解决方案，但显然，这是最慢的，但仍然是正确的（仅给出了部分点）。我将在此处附加的另一个解决方案是我使用 bisect 模块的地方，但我认为使用删除方法增加了程序的时间复杂度。我想知道是否有任何解决方案，其时间复杂度可能为 O(n log k) 时间。

from bisect import insort, bisect_left
from typing import Sequence

def min_median(s: Sequence[int], m: int) -> int:
    n = len(s)
    result = 9**30
    window = sorted(s[:m])
    mid = m // 2

    result = window[mid]
    
    for i in range(m, n):
        insort(window, s[i])
        del window[bisect_left(window, s[i - m])]
        
        
        result = min(result, window[mid])
    
    return result

Answer 1

为了在 O(n log k) 内解决这个问题，您需要找到一种方法在 O(log k) 时间内不断找到中位数，因为您需要考虑 n - k + 1 个子数组。这需要一个数据结构，当您在数组中滑动窗口时，您可以在 O(log k) 时间内插入、删除和查找所有操作的中位数。

实现此目的的一种方法是使用 AVL 树。例如，您可以使用修改后的 AVL 树，它还跟踪每个节点处子树的大小，而不仅仅是其高度。

或者，您可以考虑使用 2 棵 AVL 树：一棵用于下半部分元素，一棵用于上半部分元素。这个想法类似于两堆（如何实现中值堆）方法，但使用 AVL 树进行平衡和有序的数据插入和删除。使用 AVL 相对于堆的好处是，从 AVL 中删除只需要 O(log k)，但从堆中删除则需要 O(k)（除非您使用数组来跟踪指针），这允许您获得更好的总体时间复杂度。