c# - 获得范围补充的最快方法是什么？

Question

这个问题已经存在:

已关闭 11 年前。

Possible Duplicate:
Fastest way to get range complement

我有一个非重叠范​​围的排序数组，例如 (0,2],(2,4],(6,9] ，我希望得到它的补码 (0,12] ，它应该返回 (4,6 ],(9,12] 最快的方法是什么？

Answer 1

假设您的输入数据是以下形式的数组:

{ 0, 2, 2, 4, 6, 9 }

只需将新元素 0 和 12 添加到开头和结尾即可

{ 0, 0, 2, 2, 4, 6, 9, 12 }

并将连续对重新解释为间隔，您有:

• (0, 0]
• (2, 2]
• (4, 6]
• (9, 12]

事实上，你有退化间隔，这让事情变得一团糟，但如果你的原始列表没有任何退化间隔，你的输出列表也不会。

根据数据的格式以及是否可以进行就地修改，此操作可能是 O(1)。