使用 LINQ 在有序列表中查找"space"的最有效方法

Question

我要做的是像if这样迭代

IEnumerable<int> ids = items.Select(item => item.Id); 

即0 1 5 7

那么我想选择2，因为这是i在[0, 7+1]范围内最小的数字，这样i-1在列表中，而i不在列表中。如果0不在列表中，则选择0。

什么是最紧凑、高效、易读、花哨和简洁的方法?

Answer 1

对于非空集合，这可能是最短的可能实现，它是O(N)虽然(它也假设Id字段是数字，但不改变任何东西):

var missingIndex = list.TakeWhile((v, i) => v == i).Last() + 1;

工作原理:在列表中迭代，直到值与其索引匹配为止。如果某个值与索引不匹配，则为gap。

乌利希期刊指南

在@Rob的帮助下，修复了以非零开头的列表的处理:

var missingIndex = list.TakeWhile((v, i) => v == i).Select(i => i + 1).LastOrDefault();

对于有效的解决方案，您需要使用二进制搜索，它在命令式样式中看起来更好(参见non-linq'y)。

Answer 2

编写这样的扩展方法并不难。

    //examples
    class Program
    {
        static void Main(string[] args)
        {
            //Your original example
            var items = new List<int> { 0, 1, 5, 7 };
            var gap = items.FindFirstGap();
            Console.WriteLine(gap); //shows 2
            //No gaps
            items = new List<int> { 0, 1, 2, 3 };
            gap = items.FindFirstGap();
            Console.WriteLine(gap); //shows 4
            //no 0
            items = new List<int> { 1, 2, 3, 4 };
            gap = items.FindFirstGap();
            Console.WriteLine(gap); //shows 0
            Console.ReadLine();
        }
    }

下面的解决方案是O(N)，并支持任何结构数据类型，您可以提供一个函数来计算"+ 1"one_answers"等于"。我做了一个重载，它为你做了所有的基本整数类型逻辑，所以你不需要在调用者中指定它。

using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
    public static class ExtensionMethods
    {
        public static T FindFirstGap<T>(this IEnumerable<T> @this, Func<T, T> getNext, IEqualityComparer<T> comparer) where T : struct
        {
            using (var enumerator = @this.GetEnumerator())
            {
                T nextItem = default(T);
                while (enumerator.MoveNext())
                {
                    var currentItem = enumerator.Current;
                    if (!comparer.Equals(currentItem, nextItem))
                        return nextItem;
                    nextItem = getNext(currentItem);
                }
                return nextItem;
            }
        }
        public static T FindFirstGap<T>(this IEnumerable<T> @this, Func<T, T> getNext) where T : struct
        {
            return FindFirstGap(@this, getNext, EqualityComparer<T>.Default);
        }
        public static int FindFirstGap(this IEnumerable<int> @this)
        {
            return FindFirstGap(@this, i => i + 1, EqualityComparer<int>.Default);
        }
        public static long FindFirstGap(this IEnumerable<long> @this)
        {
            return FindFirstGap(@this, i => i + 1, EqualityComparer<long>.Default);
        }
        public static short FindFirstGap(this IEnumerable<short> @this)
        {
            return FindFirstGap(@this, i => (short)(i + 1), EqualityComparer<short>.Default);
        }
        public static byte FindFirstGap(this IEnumerable<byte> @this)
        {
            return FindFirstGap(@this, i => (byte)(i + 1), EqualityComparer<byte>.Default);
        }
    }
}

Answer 3

我的看法:

    private static int GetGap(int[] items)
    {
        // return items.TakeWhile((v, i) => v == i).Select(i => i + 1).LastOrDefault();
        if (!items.Any()) return 0;
        if (items.First() != 0) return 0;
        int counter = 0;
        return items.ToList().LastOrDefault(x => x == counter++) + 1;
    }

测试:

   public static IEnumerable TestCases
    {
        get
        {
            yield return new TestCaseData(new int[] { 0, 1, 5, 7 }, 2).SetName("1");
            yield return new TestCaseData(new int[] { 0, 1, 2, 3, 4 },5).SetName("2");
            yield return new TestCaseData(new int[] { 1, 2, 3, 4 },0).SetName("3");
            yield return new TestCaseData(new int[] { -2, -1, 1, 2, 3, 4 }, 0).SetName("4");
            yield return new TestCaseData(new int[] { -2, -1, 0, 1, 2, 3, 4 },0).SetName("5");
            yield return new TestCaseData(new int[] { 0 },1).SetName("6");
            yield return new TestCaseData(new int[] { },0).SetName("7");
        }
    }
    [TestCaseSource("TestCases")]
    public void Test(int[] items, int expected ) {
        Assert.AreEqual(expected, GetGap(items));
    }

Answer 4

对于查找第一个间隙的索引，如果符合您的要求，请尝试一下。

 int[] items = new int[] { 0,1, 3, 4, 6 }; 
 var firstGap = items.Select((index, value) => new { value, index })
                     .FirstOrDefault(c => c.value == 0 ? items[c.value] != 0 : items[c.value] != items[c.value - 1] + 1).value;