在有序序列中获得第一个缺失元素的有效方法？

Question

我有一个有序的序列,如{1,3,5,6,8,9}我想得到第一个缺少元素(示例中为2)或max()如果序列不包含缺失元素.现在我这样做:

public static int GetRegisterNumber<T>(this IQueryable<T> enumerable, Func<T, bool> whereFunc, Func<T, int?> selectFunc)
{
    var regNums = enumerable.OrderBy(selectFunc).Where(whereFunc).ToArray();

    if (regNums.Count() == 0)
    {
        return 1;
    }

    for (int i = 0; i < regNums.Count(); i++)
    {
        if (i + 1 != regNums[i])
        {
            return regNums[i].Value + 1;
        }
    }

    return regNums.Last().Value + 1;
}

但我认为有更快的方法.有什么建议？

Answer 1

编辑:我只注意到enumerable的IQueryable<T>,但selectFunc和whereFunc有型Func<T, _>.这将导致调用和调用的Enumerable版本,而不是使用数据库调用.您可能希望将它们切换为.OrderByWhereExpression<Func<T, _>>

如果您不想先订购regNums,这是一个O(n)高尔夫风格的解决方案:

var max = regNums.Max(i => (int?)i) ?? 0;
return Enumerable.Range(1, max + 1)
                 .Except(regNums)
                 .Min();

按行:

1. 通过强制转换int?,如果为空Max则返回,合并为.nullregNums0

2. 构建所有可能寄存器的序列,包括我们的下一个值(如果已满).

3. 减去当前的寄存器组.

4. 挑选最低价.

Answer 2

我可能会看下面的东西; 在Where可以做外(如可以选择要诚实):

如果您希望从1开始:

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable,
    Func<T, int> selectFunc)
{
    int expected = 1;
    foreach (T item in enumerable) {
        if (selectFunc(item) != expected) return expected;
        expected++;
    }
    return expected;
}

要从列表中的第一项开始:

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable,
    Func<T, int> selectFunc)
{
    bool first = true;
    int prev = -1;
    foreach (T item in enumerable)
    {
        int val = selectFunc(item);
        if(first) {
            prev = val;
            first = false;
        } else if (val != prev + 1) {
            return prev + 1;
        }
        prev = val;
    }
    return first ? 1 : prev + 1;
}

目前尚不清楚你想如何处理空值,所以我没有.请注意,这只迭代一次,并不缓冲所有内容.

Answer 3

假设你OrderBy和Where已应用:

int firstMissing = collection.TakeWhile((x, i) => x == ++i).LastOrDefault() + 1;