Check for missing number in sequence

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

Using Unity i have tested two solutions on set of million integers. Looks like using Dictionary and two "for" loops gives better result than Enumerable.Except

FindMissing1 Total time: 0.1420 (Enumerable.Except)
FindMissing2 Total time: 0.0621 (Dictionary and two for loops)

public static class ArrayExtension
{
    public static T[] FindMissing1<T>(T[] range, T[] values)
    {
        List<T> result = Enumerable.Except<T>(range, values).ToList<T>();
        return result.ToArray<T>();
    }

    public static T[] FindMissing2<T>(T[] range, T[] values)
    {
        List<T> result = new List<T>();
        Dictionary<T, T> hash = new Dictionary<T, T>(values.Length);
        for (int i = 0; i < values.Length; i++)
            hash.Add(values[i], values[i]);

        for (int i = 0; i < range.Length; i++)
        {
            if (!hash.ContainsKey(range[i]))
                result.Add(range[i]);
        }

        return result.ToArray<T>();
    }
}

public class ArrayManipulationTest : MonoBehaviour
{
    void Start()
    {
        int rangeLength = 1000000;
        int[] range = Enumerable.Range(0, rangeLength).ToArray();
        int[] values = new int[rangeLength / 5];
        int[] missing;
        float start;
        float duration;

        for (int i = 0; i < rangeLength / 5; i ++)
            values[i] = i * 5;

        start = Time.realtimeSinceStartup;
        missing = ArrayExtension.FindMissing1<int>(range, values);
        duration = Time.realtimeSinceStartup - start;
        Debug.Log($"FindMissing1 Total time: {duration:0.0000}");

        start = Time.realtimeSinceStartup;
        missing = ArrayExtension.FindMissing2<int>(range, values);
        duration = Time.realtimeSinceStartup - start;
        Debug.Log($"FindMissing2 Total time: {duration:0.0000}");
    }
}

Turn the range you want to check into a HashSet:

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

Will return the values that aren't in values.


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

Tags:

C#

Linq

Algorithm