7

整数のリストがあるとします:

List<int> myInts = new List<int>() {1,2,3,5,8,13,21};

整数の昇順に並べ替えられた、次に利用可能な整数を取得したいと思います。最後または最高のものではありませんが、この場合、このリストにない次の整数です。この場合、数は 4 です。

これを私に与えるLINQステートメントはありますか？次のように:

var nextAvailable = myInts.SomeCoolLinqMethod();

編集：がらくた。私は答えが 2 であるべきだと言いましたが、私は 4 を意味していました。申し訳ありません!

例: あなたがプロセス ID の配布を担当しているとします。現在のプロセス ID のリストを取得し、次のプロセス ID を発行したいのですが、次のプロセス ID は最高値に 1 を加えたものであってはなりません。むしろ、プロセス ID の順序付けられたリストから利用可能な次のものであるべきです。最高のものから始めて、次に利用可能なものを取得できますが、それは実際には問題ではありません。

4

7 に答える 7

29

カスタム拡張メソッドを記述する多くの回答が表示されますが、標準の linq 拡張メソッドと静的Enumerableクラスを使用してこの問題を解決することは可能です。

List<int> myInts = new List<int>() {1,2,3,5,8,13,21};

// This will set firstAvailable to 4.
int firstAvailable = Enumerable.Range(1, Int32.MaxValue).Except(myInts).First();
于 2012-06-19T03:13:37.967 に答える
4

@Kevin が提供する回答には、望ましくないパフォーマンス プロファイルがあります。.Countロジックは、呼び出しごとに 1 回、呼び出しごとに 1 回、.FirstOrDefault呼び出しごとに 1回、ソース シーケンスに何度もアクセスし.Containsます。IEnumerable<int>インスタンスが呼び出しの結果などの遅延シーケンスである場合.Select、これにより、数値ごとに 1 回だけでなく、シーケンスの少なくとも 2 つの計算が発生します。メソッドにリストを渡しても、チェックされた数値ごとにリスト全体が処理される可能性があります。シーケンスで実行することを想像してみて{ 1, 1000000 }ください。うまく機能しないことがわかります。

LINQ は、ソース シーケンスを 1 回だけ反復するよう努めています。これは一般的に可能であり、コードのパフォーマンスに大きな影響を与える可能性があります。以下は、シーケンスを正確に 1 回反復する拡張メソッドです。これは、連続する各ペアの差を探すことによって行われ、次の数値から 1 以上離れている最初の小さい数値に 1 が追加されます。

public static int? FirstMissing(this IEnumerable<int> numbers)
{
    int? priorNumber = null;

    foreach(var number in numbers.OrderBy(n => n))
    {
        var difference = number - priorNumber;

        if(difference != null && difference > 1)
        {
            return priorNumber + 1;
        }

        priorNumber = number;
    }

    return priorNumber == null ? (int?) null : priorNumber + 1;
}

この拡張メソッドは整数の任意のシーケンスで呼び出すことができるため、反復する前にそれらを順序付けするようにします。次に、現在の数と以前の数の差を計算します。これがリストの最初の数値である場合、priorNumbernull になるため、nulldifferenceになります。これがリストの最初の数値でない場合は、前の数値との差が正確に 1 かどうかを確認します。そうでない場合は、ギャップがあることがわかり、前の数値に 1 を追加できます。

return ステートメントを調整して、項目が 0 または 1 のシーケンスを必要に応じて処理できます。空のシーケンスの場合は null を返し、シーケンスの場合は n + 1 を返すことにしました{ n }。

于 2012-06-19T02:36:41.537 に答える
2

これはかなり効率的です。

static int Next(this IEnumerable<int> source)
{
    int? last = null;
    foreach (var next in source.OrderBy(_ => _))
    {
        if (last.HasValue && last.Value + 1 != next)
        {
            return last.Value + 1;
        }

        last = next;
    }

    return last.HasValue ? last.Value + 1 : Int32.MaxValue;
}
于 2012-06-19T02:09:36.247 に答える
0 
public static class IntExtensions
{
    public static int? SomeCoolLinqMethod(this IEnumerable<int> ints)
    {
        int counter = ints.Count() > 0 ? ints.First() : -1;

        while (counter < int.MaxValue)
        {
            if (!ints.Contains(++counter)) return counter;
        }

        return null;
    }
}

使用法：

var nextAvailable = myInts.SomeCoolLinqMethod();
于 2012-06-19T01:58:24.490 に答える
0

わかりました、これが私が思いついた解決策です。

var nextAvailableInteger = Enumerable.Range(myInts.Min(),myInts.Max()).FirstOrDefault( r=> !myInts.Contains(r));

誰かがよりエレガントなソリューションを持っている場合は、喜んでそれを受け入れます。しかし、今のところ、これが私のコードに入れて先に進むものです。

編集:これは、拡張メソッドを追加するというケビンの提案の後に実装したものです。そして、それが本当の答えでした。単一の LINQ 拡張機能では対応できないので、独自の拡張機能を追加する方が理にかなっています。それは本当に私が探していたものです。

public static int NextAvailableInteger(this IEnumerable<int> ints)
{
    return NextAvailableInteger(ints, 1); // by default we use one
}
public static int NextAvailableInteger(this IEnumerable<int> ints, int defaultValue)
{
    if (ints == null || ints.Count() == 0) return defaultValue;

    var ordered = ints.OrderBy(v => v);
    int counter = ints.Min();
    int max = ints.Max();

    while (counter < max)
    {
        if (!ordered.Contains(++counter)) return counter;
    }
    return (++counter);
}
于 2012-06-19T02:01:09.923 に答える