Проверьте наличие недостающего числа

Question

У меня есть List<int>, который содержит, например, 1,2,4,7,9.

У меня есть диапазон от 0 до 10.

Есть ли способ, чтобы определить, какие цифры отсутствуют в этой последовательности?

Я думал, LINQ может предоставить вариант, но я не могу увидеть один

В реальном мире мой список может содержать 100000 элементов таким образом производительность является ключевым

Answer 1

var list = new List<int>(new[] { 1, 2, 4, 7, 9 }); 
var result = Enumerable.Range(0, 10).Except(list); 

Answer 2

Включите диапазон, который вы хотите проверить в HashSet:

public IEnumerable<int> FindMissing(IEnumerable<int> values) 
{ 
    HashSet<int> myRange = new HashSet<int>(Enumerable.Range(0,10)); 
    myRange.ExceptWith(values); 
    return myRange; 
} 

будет возвращать значения, которые не values.

Answer 3

Метод LINQ Except был бы наиболее читаемым. Независимо от того, выполняет ли он вас адекватно или нет, это будет вопросом для тестирования.

E.g.

range.Except(listOfValues); 

Редактировать

Вот программа, которую я использовал для моего мини-теста, для других, чтобы корпеть с:

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(); 
} 

Answer 4

Создать массив элементов пит

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"); 
} 

Answer 5

 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); 
     } 

Answer 6

Если диапазон предсказуем я предлагаю следующее решение:

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

Answer 7

Это не использует 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) где п длина полного диапазона.

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; 
} 

Answer 8

Хорошо, создайте новый список, который будет параллелен исходному списку и запустит метод За исключением этого ...

Я создал полностью LinQ ответ, используя метод Aggregate вместо того, чтобы найти missings:

var list = new List<int>(new[] { 1, 2, 4, 7, 9 }); // Assumes list is ordered at this point 

list.Insert(0, 0); // No error checking, just put in the lowest and highest possibles. 
list.Add(10);  // For real world processing, put in check and if not represented then add it/them. 

var missing = new List<int>(); // Hold any missing values found. 

list.Aggregate ((seed, aggr) => // Seed is the previous #, aggr is the current number. 
{ 
    var diff = (aggr - seed) -1; // A difference between them indicates missing. 

    if (diff > 0)     // Missing found...put in the missing range. 
     missing.AddRange(Enumerable.Range((aggr - diff), diff)); 

    return aggr;  
}); 

недостающее список имеет это после того, как приведенный выше код был выполнен:

3, 5, 6, 8 

Answer 9

Альтернативный метод, который работает в целом для любой два IEnunumerable<T>, где T :IComparable. Если IEnumerables отсортированы, это работает в O (1) памяти (т. Е. Нет другого ICollection и вычитания и т. Д.) И в O (n) время.

Использование IEnumerable<IComparable> и GetEnumerator делает это немного менее читаемым, но гораздо более общим.

Реализация

/// <summary> 
/// <para>For two sorted IEnumerable&lt;T&gt; (superset and subset),</para> 
/// <para>returns the values in superset which are not in subset.</para> 
/// </summary> 
public static IEnumerable<T> CompareSortedEnumerables<T>(IEnumerable<T> superset, IEnumerable<T> subset) 
    where T : IComparable 
{ 
    IEnumerator<T> supersetEnumerator = superset.GetEnumerator(); 
    IEnumerator<T> subsetEnumerator = subset.GetEnumerator(); 
    bool itemsRemainingInSubset = subsetEnumerator.MoveNext(); 

    // handle the case when the first item in subset is less than the first item in superset 
    T firstInSuperset = superset.First(); 
    while (itemsRemainingInSubset && supersetEnumerator.Current.CompareTo(subsetEnumerator.Current) >= 0) 
     itemsRemainingInSubset = subsetEnumerator.MoveNext(); 

    while (supersetEnumerator.MoveNext()) 
    { 
     int comparison = supersetEnumerator.Current.CompareTo(subsetEnumerator.Current); 
     if (!itemsRemainingInSubset || comparison < 0) 
     { 
      yield return supersetEnumerator.Current; 
     } 
     else if (comparison >= 0) 
     { 
      while (itemsRemainingInSubset && supersetEnumerator.Current.CompareTo(subsetEnumerator.Current) >= 0) 
       itemsRemainingInSubset = subsetEnumerator.MoveNext(); 
     } 
    } 
} 

Использование

var values = Enumerable.Range(0, 11); 
var list = new List<int> { 1, 2, 4, 7, 9 }; 
var notIncluded = CompareSortedEnumerables(values, list);