LINQ找到一系列连续数字
我有一个整数列表。 我想在该列表中找到所有连续数字的运行，由起始索引和长度定义。 因此，例如，对于[1,2,3,5,7,8]输入列表，输出将是[{1,3}, {5,1}, {7,2}] 。 这很容易使用循环，像这样（未经测试的伪代码）：
for(i=1, i < maxNum; i++) { number = list[i]; previousNumber = list[i-1]; if(number - previousNumber == 1) { runLength++; } else { result.Add(startingNumber, runLength); runLength = 1; startingNumber = number; } }
但我认为可以使用LINQ。 任何想法如何做到这一点？
一种linqish方式可以编写一个扩展方法 GroupWhile如下所示（省略所有检查。未优化以便于理解。）
int[] list = new int[] { 1, 2, 3, 5, 7, 8 }; var result = list.GroupWhile((x, y) => y - x == 1) .Select(x => new {i = x.First(), len = x.Count() }) .ToList();
public static IEnumerable> GroupWhile(this IEnumerable seq, Func condition) { T prev = seq.First(); List list = new List () { prev }; foreach(T item in seq.Skip(1)) { if(condition(prev,item)==false) { yield return list; list = new List (); } list.Add(item); prev = item; } yield return list; }
TODO：使用IGrouping 🙂
这似乎是一种合理的方法：
- 使用
Range对原始列表进行压缩，因此每个元素都使用其索引进行元组处理 - 选择那些列表前置不是其自然前身的元素
- 转换为数组并保存到临时变量（以方便最后一步）。
- 从索引中减去子数组的长度。 对于最后一项，它与原始列表长度不同。 对于其他项目，它与下一个索引的区别。
var list = new int[] { 1, 2, 3, 5, 7, 8 }; var filtered = list.Zip(Enumerable.Range(0, list.Length), Tuple.Create) .Where((x, i) => i == 0 || list[i - 1] != x.Item1 - 1).ToArray(); var result = filtered.Select((x, i) => i == filtered.Length - 1 ? Tuple.Create(x.Item1, list.Length - x.Item2) : Tuple.Create(x.Item1, filtered[i + 1].Item2 - x.Item2)); foreach (var t in result) { Console.WriteLine(t); }
这导致了
(1, 3) (5, 1) (7, 2)
是否有人要求将解决方案变为可疑可读性的LINQ查询？
var serieses = input.Aggregate( new List>(), (l, i) => { var last = l.LastOrDefault(); if (last == null || last.Item1 + last.Item2 != i) { l.Add(new Tuple(i, 1)); } else if (last.Item1 + last.Item2 == i) { l.RemoveAt(l.Count - 1); l.Add(new Tuple(last.Item1, last.Item2 + 1)); } return l; }, l => l);
没有这种开箱即用的扩展方法，但你可以自己创建：
public static class LinqUtils{ public class ConsecutiveGroup { public T Left { get; internal set; } public T Right { get; internal set; } public long Count { get; internal set; } } public static IEnumerable> ConsecutiveCounts (this IEnumerable src, Func consecutive) { ConsecutiveGroup current = null; foreach (var s in src) { if (current==null) { current = new ConsecutiveGroup { Left = s, Right = s, Count = 1 }; continue; } if(consecutive(current.Right, s)) { current.Right = s; current.Count += 1; continue; } yield return current; current = new ConsecutiveGroup { Left = s, Right = s, Count = 1 }; } if (current!=null) { yield return current; } } } [TestFixture] public static class LinqUtilsTests { [Test] public void TestConsecutiveCounts() { var src = new[] {1,2,3,5,7,8}; var expected = new[] { Tuple.Create(1, 3), Tuple.Create(5, 1), Tuple.Create(7, 2) }; var result = src .ConsecutiveCounts((prev, current) => current == (prev + 1)) .Select(c=>Tuple.Create(c.Left, c.Count)); Assert.IsTrue(expected.SequenceEqual(result)); } }
您需要某种方法来扫描序列，累积结果然后对它们进行分组。 首先是一个简单的Scan扩展方法（类似于Aggregate但它输出中间结果）（对于IObservable存在Scan方法，但对于IEnumerable不存在）：
public static IEnumerable Scan(this IEnumerable input, Func next, U state) { yield return state; foreach (var item in input) { state = next(state, item); yield return state; } }
并使用此方法和Zip扩展方法，执行以下操作：
var ints = new[] { 1, 2, 3, 5, 7, 8, 10 }; var result = ints // Zip the list with itself shifted 1 to the left (add dummy value at the end) // and calculate the difference between each consecutive value. .Zip(ints .Skip(1) .Concat(new[] { int.MaxValue }), (i0, i1) => new { i = i0, diff = i1 - i0 }) // Reverse because it's far easier keeping track of the group we're at .Reverse() // Scan through the list, assigning an incremental group number to each // consecutive sequence .Scan((state, z) => state == null ? Tuple.Create(zi, z.diff, 0) : Tuple.Create(zi, z.diff, z.diff > 1 ? state.Item3 + 1 : state.Item3), (Tuple) null) // <-- dummy starting state. // Skip the dummy starting state we started the scan with .Skip(1) // Reverse back .Reverse() // Group by the group numbers we assigned during the scan .GroupBy(t => t.Item3, (i, l) => new { l.First().Item1, l = l.Count() });