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）？
谢谢你。
注意：这不是家庭作业。我的自定义数据库实现事务需要这个。我一个人学编程。
好的，我知道你打算用这个去哪里。
Lucene使用非常大的位域来做到这一点。
假设您可能的数字范围从 1 到 64，这些数字中的每一个都对应于 64 位 int 上该位置的位。（第 1 位是第 0 位，第 2 位是第 1 位）。
如果将数字添加到范围，则打开该位（在您的示例中，您将打开位 0 到 4 和 19 到 29）。
现在要检查一个数字范围，您创建另一个 64 位 int 并打开该范围的位，并在两个位字段上执行按位与 (&)。结果中的 1 位是重叠范围。
对于超过 64 的数字，只需按比例增加位数（可能通过使用数组或整数列表）
希望这可以帮助 ：）
更新：可扩展性
假设您正在研究 64 位架构，并且您可以在一次操作中对 64 位整数进行 AND 运算。理想情况下，您会使用 64 位整数。
现在，假设您可能的数字范围从 1 到 64,000，为此您需要 1000 个 64 位整数。
现在让我们看几个用例
我想检查 70 - 80 的范围。为此，我们不需要另外 1000 个整数进行检查，只需一个整数，我们知道我们正在检查数组中的第二个元素。
我想检查 2000 - 10,000 的范围同样，我们只需要一个 int，计算它在数组 31st 中的位置（我认为）并相应地设置位并进行比较。然后遍历列表，直到达到 10,000（位置 156？），沿途进行比较，并构建要返回的整数列表。
更新 2：那不是 O(1)
根据要检查的范围的大小，您可以将其实现为 O(1)
但是使用这种算法，一般情况仍然是 O(n)
使用 HashSet<T>：
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
但它应该让你走上正轨。
如果您将范围本身存储在 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;
}
}
}
O(n) 表示随着元素的数量而变化 O(1) 表示恒定时间
我也想不出实现这一点的 O(1) 方式。
我不确定该应用程序的具体细节，但我的直觉告诉我这在数据库中会更好地处理，因为它是基于集合的操作。
IE
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range
如果您尝试以迭代方式解决此问题，那可能会有所帮助。例如，使用 Ranges 列表加载 LineNumber 类，这些范围中有一个 start 和 end int。然后代替“checkrange(a,b)”方法，只需实现一个“hasNumber(a)”方法。只需遍历 Ranges 列表并在 Range 类上调用方法 'isInRange(a) 即可做到这一点，因此您的 Data 模型可能是：
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 实现留待以后使用。:)
这不是一个完整的解决方案，但也许一种不同的方法可以帮助产生更好的结果。