algorithm - 查找包含来自总体 A 的最大元素和来自总体 B 的零元素的标量区间

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

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

标签： algorithmdata-structuresheapintervals

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

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

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

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

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