Questo non fa uso di LINQ ma funziona in tempo lineare.
Suppongo che l'elenco di input sia ordinato.
Questo richiede O(list.Count)
.
private static IEnumerable<int> get_miss(List<int> list,int length)
{
var miss = new List<int>();
int i =0;
for (i = 0; i < list.Count - 1; i++)
{
foreach (var item in
Enumerable.Range(list[i] + 1, list[i + 1] - list[i] - 1))
{
yield return item;
}
}
foreach (var item in Enumerable.Range(list[i]+1,length-list[i]))
{
yield return item;
}
}
Questo dovrebbe prendere O(n)
dove n è la lunghezza della gamma completa.
static void Main()
{
List<int> identifiers = new List<int>() { 1, 2, 4, 7, 9 };
Stopwatch sw = new Stopwatch();
sw.Start();
List<int> miss = GetMiss(identifiers,150000);
sw.Stop();
Console.WriteLine("{0}",sw.ElapsedMilliseconds);
}
private static List<int> GetMiss(List<int> identifiers,int length)
{
List<int> miss = new List<int>();
int j = 0;
for (int i = 0; i < length; i++)
{
if (i < identifiers[j])
miss.Add(i);
else if (i == identifiers[j])
j++;
if (j == identifiers.Count)
{
miss.AddRange(Enumerable.Range(i + 1, length - i));
break;
}
}
return miss;
}
fonte
2010-03-19 08:37:28
Come indicato in un commento ad Andras, un intervallo di 1 milione di int, e un elenco di 100.000, con eccezione (sulla mia macchina) richiede 0,25 secondi. Ma non abbiamo modo di sapere se questo è abbastanza performante per te (e se no, quali sono i limiti accettabili per le prestazioni?) –