查找包含总体A中最大元素和总体B中零元素的标量区间

创建一个包含所有值的单个列表,其中每个值都标记有两个计数:一个与集合a相关,另一个与集B相关。最初,当值来自集合a时,这些计数为1和0,当值来源于集合B时,计数为0和1。因此,此列表中的条目可以是元组(value、countA、countB)。此操作为O(n)。

对这些元组进行排序。O(nlogn)

将具有重复值的元组合并为一个元组,并将值累积在相应的计数器中,使元组告诉我们该值在集合A中出现了多少次,在集合B中出现了几次。O(n)

按排序顺序遍历此列表,并保持一系列相邻元组中countA的最大计数和,其中countB始终为0,以及该范围的最小值和最大值。O(n)

排序是时间复杂度的决定因素:O(nlogn)。

按O对A和B进行排序(|A|log|A|+|B|log|B|)。然后应用以下算法,其复杂度为O(|A|+|B|):

i = j = k = 0
best_interval = (0, 1)

while i < len(B) - 1:
    lo = B[i]
    hi = B[i+1]
    
    j = k    # We can skip ahead from last iteration.
    while j < len(A) and A[j] <= lo:
        j += 1

    k = j   # We can skip ahead from the above loop.
    while k < len(A) and A[k] < hi:
        k += 1

    if k - j > best_interval[1] - best_interval[0]:
        best_interval = (j, k)
    
    i += 1

x0 = A[best_interval[0]]
x1 = A[best_interval[1]-1]

第一次检查时,它可能看起来是二次的,但请注意,我们永远不会减少 j 和 k -这实际上只是三个指针的线性扫描。