Проверять отсутствие числа в последовательности

Ответ 1

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

Ответ 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.

Ответ 3

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

например.

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

Альтернативный метод, который работает вообще для любого двух 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);

Ответ 7

Этот метод не использует LINQ и работает в целом для любых двух IEnunumerable<T> where T :IComparable

public static IEnumerable<T> FindMissing<T>(IEnumerable<T> superset, IEnumerable<T> subset) where T : IComparable
{
    bool include = true;
    foreach (var i in superset)
    {
        foreach (var j in subset)
        {
            include = i.CompareTo(j) == 0;
            if (include)
                break;
        }
        if (!include)
            yield return i;
    }
}

Ответ 8

Это не использует 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;
}

Ответ 9

Хорошо, действительно, создайте новый список, который будет параллелен исходному списку и запустит метод Except over it...

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

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

Ответ 10

этот метод возвращает количество отсутствующих элементов, сортирует набор, добавляет все элементы из диапазона от 0 до диапазона max, затем удаляет исходные элементы, после чего у вас будет отсутствующий набор

int makeArrayConsecutive(int[] statues) 
{    

Array.Sort(statues);

HashSet<int> set = new HashSet<int>();

for(int i = statues[0]; i< statues[statues.Length -1]; i++)
{
    set.Add(i);
}

   for (int i = 0; i < statues.Length; i++)
{
    set.Remove(statues[i]);
}

var x = set.Count;

return x;
// return set ; // use this if you need the actual elements + change the method return type 

}

Ответ 11

Создайте массив num items

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