Я имею List<int>
который содержит 1,2,4,7,9, например.
У меня есть диапазон от 0 до 10.
Существует ли способ определить то, что числа пропускают в той последовательности?
Я думал, что LINQ мог бы предоставить возможность, но я не вижу тот
В реальном мире мой Список мог содержать 100 000 объектов, таким образом, производительность является ключевой
var list = new List<int>(new[] { 1, 2, 4, 7, 9 });
var result = Enumerable.Range(0, 10).Except(list);
Если диапазон предсказуем, я предлагаю следующее решение:
public static void Main()
{
//set up the expected range
var expectedRange = Enumerable.Range(0, 10);
//set up the current list
var currentList = new List<int> {1, 2, 4, 7, 9};
//get the missing items
var missingItems = expectedRange.Except(currentList);
//print the missing items
foreach (int missingItem in missingItems)
{
Console.WriteLine(missingItem);
}
Console.ReadLine();
}
С уважением, y00daa
Это не использует LINQ, но работает в линейном времени.
Я предполагаю, что список ввода отсортирован.
Это занимает 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;
}
}
Это должно занять O (n)
, где n - длина полного диапазона.
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;
}
Создать массив из num элементов
const int numItems = 1000;
bool found[numItems] = new bool[numItems];
List<int> list;
PopulateList(list);
list.ForEach( i => found[i] = true );
// now iterate found for the numbers found
for(int count = 0; i < numItems; ++numItems){
Console.WriteList("Item {0} is {1}", count, found[count] ? "there" : "not there");
}
Метод LINQ Except
будет наиболее читабельным. Будет ли он работать адекватно для вас или нет - вопрос для тестирования.
Например,
range.Except(listOfValues);
Edit
Вот программа, которую я использовал для своего мини-бенчмарка, чтобы другие могли поработать с ней:
static void Main()
{
var a = Enumerable.Range(0, 1000000);
var b = new List<int>();
for (int i = 0; i < 1000000; i += 10)
{
b.Add(i);
}
Stopwatch sw = new Stopwatch();
sw.Start();
var c = a.Except(b).ToList();
sw.Stop();
Console.WriteLine("Milliseconds {0}", sw.ElapsedMilliseconds );
sw.Reset();
Console.ReadLine();
}
List<int> selectedNumbers = new List<int>(){8, 5, 3, 12, 2};
int firstNumber = selectedNumbers.OrderBy(i => i).First();
int lastNumber = selectedNumbers.OrderBy(i => i).Last();
List<int> allNumbers = Enumerable.Range(firstNumber, lastNumber - firstNumber + 1).ToList();
List<int> missingNumbers = allNumbers.Except(selectedNumbers).ToList();
foreach (int i in missingNumbers)
{
Response.Write(i);
}
Превратите диапазон, который вы хотите проверить, в HashSet:
public IEnumerable<int> FindMissing(IEnumerable<int> values)
{
HashSet<int> myRange = new HashSet<int>(Enumerable.Range(0,10));
myRange.ExceptWith(values);
return myRange;
}
Вернет значения, которых нет в значениях
.