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

Question

给定两个标量（浮点）值的大集合 A 和 B，您将使用什么算法来找到包含 B 中的零个元素和 A 中的最大元素数的（标量）范围 [x0,x1] ？

排序复杂度(O(n log n))是不可避免的吗？

Answer 1

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

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

将重复值的元组合并为一个元组，并将值累加到对应的计数器中，这样元组就告诉我们这个值在集合A中出现了多少次，在集合B中出现了多少次。O(n)

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

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

Answer 2

在 O(|A| log |A| + |B| log |B|) 中对 A 和 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 - 它实际上只是一个具有三个指针的线性扫描。

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

Find scalar interval containing maximum elements from population A and zero elements from population B

algorithm

heap

intervals

data-structures