如何检查 int 类型的索引序列是否连续？

Question

我有一个 Column class，其中有一个 Index 属性 int.

如果我有一个 Column 对象的集合，我正在寻找一种方法来测试它们的索引是否连续。连续是指索引彼此相邻，因此如果按值排序，它们与下一个和上一个索引相差 1。

可以有任意数量的 column 个对象。

因此，例如：

10,11,12,13 => 真
3,5,7 => 假
1,2,4 => 假

编辑

虽然这些示例是有序索引，但我想要一个采用无序索引集的解决方案。

我确信可能有一种巧妙的 Linq 方法可以解决这个问题，但我看不到它。

用代码表示：

public class Column 
{
    public int Index { get; set; }
}

class Program
{
    static void Main(string[] args)
    {
        // Example set of columns 1
        List<Column> columns1 = new List<Column>()
        {
            new Column(){Index = 10},
            new Column(){Index = 11},
            new Column(){Index = 12},
            new Column(){Index = 13},
        };

        // Example set of columns 2
        List<Column> columns2 = new List<Column>()
        {
            new Column(){Index = 3},
            new Column(){Index = 5},
            new Column(){Index = 7},
        };

        // Example set of columns 3
        List<Column> columns3 = new List<Column>()
        {
            new Column(){Index = 1},
            new Column(){Index = 2},
            new Column(){Index = 4},
        };

        var result1 = IndicesAreContiguos(columns1); // => true
        var result2 = IndicesAreContiguos(columns2); // => false
        var result3 = IndicesAreContiguos(columns3); // => false
    }

    public bool IndicesAreContiguos(IEnumerable<Column> columns) 
    {
        // ....???
    }

}

Answer 1

一种方法是创建从最小值到最大值的范围并将其与现有索引进行比较：

public static bool IndicesAreContiguos(IEnumerable<Column> columns)
{
    var orderedIndices = columns.Select(c => c.Index).OrderBy(i => i);
    if (orderedIndices.Distinct().Count() != columns.Count()) return false;  // Optional.

    int min = columns.Min(c => c.Index);
    int max = columns.Max(c => c.Index);

    return Enumerable.Range(min, max - min + 1).SequenceEqual(orderedIndices);
}

Answer 2

试一试：

public static bool IndicesAreContiguos(IEnumerable<Column> columns)
{
    var ordered = columns.Select(x => x.Index).OrderBy(x => x).ToArray();
    return ordered.Skip(1).Zip(ordered, (x, y) => x - y).All(z => z == 1);
}

字面意思是"ordered by value they are 1 apart from the next and previous Index."

Answer 3

为此您不需要 LINQ

public bool IsContig(int[] arr) {
  for(int i = 1; i<arr.Length;i++)
    if(arr[i] - arr[i-1] != 1)
      return false;
  return true;
}

LINQ 是一把锤子，但不是每个问题都是钉子

（编辑：接受一组无序的索引，然后考虑首先对数组进行排序的修改。同样，LINQ 不是必需的；Array.Sort 可以工作）

如果 1,2,3,2,3,2,3,4,3,2,3,4,5,4,5 的序列是连续的，则改进 IF 以允许结果为-1 太

Answer 4

通过数学，您可以创建一个函数来处理无序集合，只需对集合进行一次迭代。

public static bool IsConsecutive(this IEnumerable<int> values)
{
    return values
        .Aggregate((Sum: 0, Min: int.MaxValue, Max: int.MinValue, Count: 0), 
            (total, value) =>
            {
                total.Count += 1;
                total.Sum += value;
                total.Min = total.Min > value ? value : total.Min;
                total.Max = total.Max < value ? value : total.Max;

                return total;
            },
            (total) =>
            {
                var difference = total.Max - total.Min + 1;
                var expectedSum = (total.Count * (total.Min + total.Max)) / 2;

                return difference == total.Count && expectedSum == total.Sum;
            });
}

解法基于连续整数和的公式（高斯公式）

$\sum=\frac{n(a_{1} + a_{n})}{2}$

但是因为公式可以应用于步长不是 1 的连续整数（例如 2、4、6、8），我们添加了通过计算最小值和最大值之间的差异并进行比较来检查步长是否只有一个与值的数量。

用法

var values = new[] { 10, 12, 13, 15, 14, 11 };

if (values.IsConsecutive())
{
    // Do something
}

如何检查 int 类型的索引序列是否连续？

How can I check that a sequence of indices of type int are contiguous?

c#

linq

morelinq

编辑