题
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)?
谢谢。
注意:这是 NOT 作业。我需要这个用于我的自定义数据库实现事务。我正在学习编程单独。
其他提示
使用HashSet <!> lt; T <!> gt;:
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
但它应该让你走上正轨。
好的,我知道你要去哪里了。
Lucene 使用非常大的位字段执行此操作。
假设您的可能数字范围从1到64,这些数字中的每一个都对应于64位int上该位的位。 (No 1为0位,No 2为1位)。
如果你在一个范围内添加一个数字,你可以打开那个位(在你的例子中,你可以打开0到4位和19到29位)。
现在要检查一系列数字,你可以创建另一个64位int,并打开该位范围,并在两个位字段上执行按位And(<!> amp;)。结果中的1位是重叠范围。
对于64以上的数字,只需扩大位数(可能通过使用数组或整数列表)
希望这会有所帮助:)
更新:可扩展性
假设您正在使用64位架构,并且您可以在一次操作中使用AND 64位整数。理想情况下,您使用64位整数。
现在,假设您可能的数字范围从1到64,000,为此您需要1000 64位整数。
现在让我们看几个用例
-
我想查看70 - 80的范围。 要做到这一点,我们不需要另外1000个int来进行检查,只需要一个int,我们知道我们正在检查数组中的第二个元素。
-
我想检查2000 - 10,000的范围 同样,我们只需要一个int,计算它在数组31st中的位置(我认为)并相应地设置位并进行比较。然后你遍历列表,直到你达到10,000(位置156?),沿途比较,并建立你要返回的整数列表。
醇>
更新2 :这不是O(1)
根据要检查的范围的大小,您可以将其实现为O(1)
然而,使用这种算法,一般情况仍然是O(n)
如果将范围本身存储在NumberLine中,该怎么办?添加重叠范围时可以进行合并。 然后CheckRange可以查询存储在NumberLine中的范围而不是单个元素。然后,这变为范围数中的O(N),而不是元素数量中的O(N)。如果在可能的情况下进行合并范围,则范围的数量将小于对AddRange的调用次数。
请参阅下面的代码示例。我不是.Net集合的专家,所以通过选择更好的集合类型可以实现更高效的实现。 _NT 建议在树结构中存储值。您也可以将其应用于范围并按起始编号存储它们。这使得在添加和检查时更快地搜索范围。在我目前的实现中,将Ranges添加到结尾比在开头添加范围慢。将其存储在有效树中时,复杂度在范围数内变为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)方式。
我不确定该应用程序的细节,但我的直觉告诉我在数据库中处理得更好,因为它是基于集合的操作。
即
Select
*
from numberlines
where
number_group = @group_id
marked = 1
and number >= @min_range
and number <= @max_range
如果你试图在迭代中解决这个问题可能有所帮助。例如,使用范围列表加载LineNumber类,这些范围中包含start和end int。然后,而不是'checkrange(a,b)'方法,只需实现'hasNumber(a)'方法。只需循环遍历Ranges列表并在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实现以供日后使用。 :)
这不是一个完整的解决方案,但也许一种不同的方法可以帮助产生更好的结果。