数轴的 AC# 实现

Question

NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);

line.CheckRange(10, 25);

NumberLine 是一个表示数轴的类。我想在上面标记不同范围的数字。 CheckRange 方法应该返回 10-25 中我标记的部分和我没有标记的部分。在这种情况下，它应该返回 10-20 未标记，并且 20-25 已标记。

我怎样才能有效地实现这一点，这不会做 o(n) ？

谢谢。

注意：这不是家庭作业。我需要这个用于我的自定义数据库实现事务。我正在独自学习编程。

Answer 1

解决方案很简单：将所有突出显示的值添加到 AVL 或 红黑树。我的意思是，当您执行 AddRange(1,3) 时，将整数值 1,2 和 3 插入树中。

检查范围时，只需查找端点值即可。这需要O(log n)，比 O(n) 快得多。

注意：插入和删除都需要O(log n)。

Answer 2

使用 HashSet：

public class NumberLine : HashSet<int>
{
    public void AddRange(int start, int end)
    {
        int count = (end-start)+1;

        UnionWith(Enumerable.Range(start, count));
    }

    public IEnumerable<int> CheckRange(int start, int end)
    {
        NumberLine other = new NumberLine();

        other.AddRange(start, end);

        other.IntersectWith(this); // marked
        // other.ExceptWith(this); // not marked

        return other;
    }
}

不确定您想要从 CheckRange 返回什么，或者您是否只是希望它打印一个字符串。对于像您指定的范围这样简单的事情，您可以使用：

public string CheckRange(int start, int end)
{
    NumberLine other = new NumberLine();

    other.AddRange(start, end);

    IEnumerable<int> marked = other.Intersect(this);
    IEnumerable<int> notMarked = other.Except(this);

    int markedMin = marked.Min();
    int markedMax = marked.Max();
    int notMarkedMin = notMarked.Min();
    int notMarkedMax = notMarked.Max();

    string markedString = (markedMin == markedMax)
            ? markedMin.ToString()
            : string.Format("{0} - {1}", markedMin, markedMax);

    string notMarkedString = (notMarkedMin == notMarkedMax)
            ? notMarkedMin.ToString()
            : string.Format("{0} - {1}", notMarkedMin, notMarkedMax);

    return string.Format("Marked: {0}\r\nNot Marked: {1}", markedString, notMarkedString);
}

它不会处理像这样的分割范围：

Marked: 10-15, 20-25
Not Marked: 16-19

但它应该让您走上正确的轨道。

Answer 3

好的，我明白你要做什么了。

Lucene 使用非常大的位字段来执行此操作。

假设您可能的数字范围是从 1 到 64，这些数字中的每一个都对应于 64 位 int 上该位置的位。 （No 1 是位 0，No 2 是位 1）。

如果将数字添加到范围中，则打开该位（在您的示例中，您将打开位 0 到 4 以及 19 到 29）。

现在要检查数字范围，您可以创建另一个 64 位 int，并打开该范围的位，并对两个位字段执行按位与 (&)。结果中的 1 位是重叠范围。

对于超过 64 的数字，只需增加位数（可能通过使用数组或整数列表）

希望这有帮助:)

更新：可扩展性

假设您正在使用 64 位架构并且您可以在一次操作中对 64 位整数进行 AND 运算。理想情况下您会使用 64 位整数。

现在，假设您可能的数字范围是从 1 到 64,000，为此您需要 1000 个 64 位整数。

现在让我们看几个用例

1. 我想检查 70 - 80 的范围。
   为此，我们不需要另外 1000 个整数进行检查，只需一个整数，并且我们知道我们正在对照数组中的第二个元素对其进行检查。

2. 我想检查 2000 - 10,000 的范围
   同样，我们只需要一个 int，计算它在数组第 31 位中的位置（我认为）并相应地设置位并进行比较。然后迭代列表，直到达到 10,000（位置 156？），一路进行比较，并构建要返回的整数列表。

更新 2：这不是 O(1)

根据要检查的范围的大小，您可以将其实现为 O(1)

但是使用此算法，一般情况仍然是 O(n)

Answer 4

如果将范围本身存储在 NumberLine 中会怎么样？添加重叠范围时，您可以进行合并。
然后，CheckRange 可以查询存储在 NumberLine 内的范围而不是单个元素。然后，范围数量变为 O(N)，而不是元素数量 O(N)。如果您在可能的情况下合并范围，则范围的数量将小于对 AddRange 的调用数量。

请参阅下面的代码示例。我不是 .Net 集合方面的专家，因此通过选择更好的集合类型可以实现更有效的实现。 _NT 建议将值存储在树结构中。您也可以将其应用于范围并按起始编号存储它们。这使得在添加和检查时都可以更快地搜索范围。在我当前的实现中，在末尾添加范围比在开头添加范围慢。当将其存储在高效树中时，范围数量的复杂性变为 O(log N)。

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;

namespace NumberLine
{
    class Program
    {
        static void Main(string[] args)
        {
            NumberLine line = new NumberLine();
            line.AddRange(1, 5);
            line.AddRange(10, 12);
            line.AddRange(20, 30);

            List<Range> ranges = line.CheckRange(10, 25);
            foreach (Range r in ranges)
            {
                for (int i = r.Start; i <= r.End; i++)
                {
                    Console.WriteLine(i);
                }
            }
        }
    }

    class Range
    {
        public int Start;
        public int End;
    }

    class NumberLine
    {
        private SortedList<int, Range> Ranges = new SortedList<int, Range>();

        public void AddRange(int start, int end)
        {
            if (Ranges.Count == 0)
            {
                 Ranges.Add(start, new Range() { Start = start, End = end });
            }
            else
            {
                foreach (Range currentRange in Ranges.Values)
                {
                    if (start <= currentRange.Start) 
                    {
                        if (end >= currentRange.End)
                        {
                            currentRange.Start = start;
                            currentRange.End = end;
                        }
                        else
                        {
                            currentRange.Start = start;
                        }
                        Ranges.RemoveAt(start);
                        Ranges.Add(start, currentRange);
                        break;
                    } 
                    else
                    {
                        if (start <= currentRange.End)
                        {
                            currentRange.End = end;
                            break;
                        }
                        else
                        {
                            Ranges.Add(start, new Range(){ Start = start, End = end });
                            break;
                        }
                    }
                }           
            }
        }

        public List<Range> CheckRange(int start, int end)
        {
            List<Range> result = new List<Range>();
            foreach (Range currentRange in Ranges.Values)
            {
                if (start <= currentRange.End)
                {
                    if (end <= currentRange.End)
                    {
                        result.Add(new Range() { Start = currentRange.Start, End = end });
                        break;
                    }
                    else
                    {
                        if (start <= currentRange.Start)
                        {
                            result.Add(new Range() { Start = currentRange.Start, End = currentRange.End });
                        }
                        else
                        {
                            result.Add(new Range() { Start = start, End = currentRange.End });
                        }
                    }
                }
            }
            return result;
        }
    }

}

Answer 5

O(n) 意味着随着元素数量的变化而变化
O(1) 意味着恒定时间，

我也想不出 O(1) 的实现方式。

Answer 6

我不确定该应用程序的具体细节，但我的直觉告诉我，这在数据库中处理会更好，因为它是基于集合的操作。

IE

Select
*
from numberlines
where 
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range

Answer 7

如果您尝试迭代地解决这个问题，这可能会有所帮助。例如，使用范围列表加载 LineNumber 类，这些范围中有一个开始和结束 int。然后，只需实现“hasNumber(a)”方法，而不是“checkrange(a,b)”方法。只需循环遍历范围列表并调用 Range 类上的方法“isInRange(a)”即可完成此操作。因此，您的数据模型可能是：

LineNumber {
 List<Range> ranges;
 aadRange(a,b);
 // Loops through all ranges and calls isInRange on each method
 isInRange(a);

 //just iterates over isInRange from a to b
 checkRange(a,b)

}

Range {
 Range(a,b)
 isInRange(a);
}

这将为您提供一些工作代码和一个接口。它可能不够快，但你还不知道。 lucene 的实现留到以后再说。 :)

这不是一个完整的解决方案，但也许不同的方法可以帮助产生更好的结果。