代码之家  ›  专栏  ›  技术社区  ›  Idan

求数组内部间隔的算法

  •  1
  • Idan  · 技术社区  · 15 年前

    我有一个包含n个间隔的列表 [0,1]

    每个间隔看起来像 [a(i),b(i)] 0<=a(i)<b(i)<=1 , i = 1...n

    如果n个区间包含在其他区间内,我需要找到一个有效的算法来确定每个区间。

    我尝试了许多选择,但在o中只能找到一个(n^2)

    有什么建议吗?

    3 回复  |  直到 12 年前
        1
  •  2
  •   danben    15 年前

    提示:对列表进行排序。

        2
  •  1
  •   Permaquid    15 年前

    假设只有一个区间[0,1]。如果它不在你的列表中只是为了方便而添加它。

    对端点进行排序。如果两个端点相等,请在相应的右端点上反向排序。因此[0.1,0.2],[0.1,0.3]将被排序为0.1,0.1,0.2,0.3,其中第一个0.1与第二个间隔。同样,如果右端点相等。

    每个端点都应该有对其间隔的引用,这样您就可以找到给定端点的间隔。

    扫描已排序的终结点。像你一样,造一棵树。使用[0,1]作为根。节点可以是红色或绿色。一开始是红色的。所以根节点最初是红色的。

    树的概念是,最终,如果一个间隔包含另一个间隔,它将成为树中的祖先。如果两个间隔不重叠或部分重叠,它们将位于不同的分支中,并且它们唯一的共同祖先将是根,或包含它们的其他间隔。

    当遇到每个左端点时,通过将其间隔的红色节点添加到当前树节点,将其添加到树中的暂定位置。因此,我们遇到的第一个端点会导致相应的间隔被添加到根节点下,并成为当前节点。因此,在遇到其右端点之前,树节点可能有多个附加到它的节点。

    当遇到右端点时,其节点将变为绿色,因为我们已经将其从一端完全覆盖到另一端。如果它有任何红色的子节点,则必须移动它们,因为虽然刚刚变绿的节点包含其左端,但它不包含其右端。所以我们将它们全部移到父节点(父节点必须仍然是红色)。

    我们继续这个过程,直到到达1.0端点。此时树已完成。所有节点均为绿色。每个节点下的节点表示相应间隔包含的间隔。

        3
  •  1
  •   Tea-man    12 年前
    1. 根据中断连接的起始点对间隔进行排序,以使较早的端点在稍后出现
    2. 注意,按照排序顺序,对于每个元素e,包含e的间隔只能存在于其左侧。
    3. 因此,从左开始线性扫描,跟踪到目前为止观察到的最大端点。在任何阶段,如果当前间隔的端点小于最大端点,我们都会找到一个包含在其他端点中的间隔。