5

我有一个范围列表。每个范围都有一个 from 和 to 值，这意味着该值可以介于该范围之间。例如，如果范围是 (1,4)。，值可以是 1,2,3 和 4。现在，我需要在给定的范围列表中找到不同的值。下面是示例代码。

class Program
{
    static void Main(string[] args)
    {
        List<Range> values = new List<Range>();
        values.Add(new Range(1, 2));
        values.Add(new Range(1, 3));
        values.Add(new Range(1, 4));
        values.Add(new Range(3, 5));
        values.Add(new Range(7, 10));
        values.Add(new Range(7, 8));

        // Expected Output from the range of values
        //1,2,3,4,5,7,8,9,10
    }
}
class Range
{
    public Range(int _form, int _to)
    {
        from = _from;
        to = _to;
    }
    private int from;

    public int From
    {
        get { return from; }
        set { from = value; }
    }

    private int to;

    public int To
    {
        get { return to; }
        set { to = value; }
    }

}

我可以遍历每个范围并找到不同的值。但是，如果有人可以提供一种有效的方法，那将很有帮助。

4

3 回答 3

4
  • 对于少数间隔，直接的方法应该可以解决问题。
  • 如果大多数间隔相互折叠，您可以执行合并它们的初步步骤以减少测试次数
  • 如果不相交区间的数量很高，请构建一个区间树。这是一篇带有 Java 代码示例的文章的链接。
于 2012-08-08T14:39:30.483 回答
1

请考虑以下解决方案（我不会写完整的代码，只写一般路线）：

  • 对于每个传入范围调整 MinVal 和 MaxVal 变量 - 分别保持所有范围中的最小值和所有范围中的最大值
  • 建立两个传入范围的集合，让一个名字成为另一个Begins名字Ends
  • 收集所有 Ranges 后对两个集合进行排序：Begins应按from值排序，Ends应按to值排序
  • depth将计数器变量初始化为 0
  • 初始化BeginPointer并EndPointer到各个集合的第一个元素
  • 现在是关键部分：从MinValto迭代MaxVal，如果当前值指示收集的开始（当前BeginPointer的数字等于迭代值）-> 增加depth1 并向前移动BeginPointer（重复连续的“开始”）
  • 如果depth大于 0 -> 打印当前迭代值，因为我们在某个范围内
  • 如果当前值指示收集结束 -> 减depth1（重复连续“结束”）

这将适用于更大范围的值。如果最大值相对较低（即 1000，如评论中的 OP 所示 - 请参阅我的其他答案）。

于 2012-08-08T14:48:27.140 回答
1

如果_from和的范围_to很小（如所示为 1000），则可以使用布尔数组 [1000]。对于每个传入的 Range，将相应的数组元素设置为 true。即对于 Range(3,6)，将数组元素 3、4、5 和 6 设置为 true。现在遍历数组并打印每个为真的索引。对于小范围应该足够有效。

于 2012-08-08T14:58:36.880 回答