查找列表中最长的序列<；int>；

本文关键字：lt int gt 列表 查找 | 更新日期: 2023-09-27 17:54:56

我有以下列表：

List<int> days = new List<int> { 1, 4, 5, 6, 7, 8, 20, 24, 25, 26, 30 };

我想得到最长序列的开始和结束数字。对于上面的例子，我应该得到(4，8(。如果有两个长度相同的序列，我想要第一个。

注意：列表中的数字总是按递增顺序排列。

到目前为止，我已经尝试过这个：

List<Tuple<int, int>> seqs = new List<Tuple<int, int>>();
int _start = 0;
for (int i = 0; i <= days.Count; i++)
{
    if (i == 0)
    {
        _start = days[i];
        continue;
    }
    if (i < days.Count)
    {
        if (days[i] == days[i - 1] + 1)
            continue;
        else
        {
            seqs.Add(new Tuple<int, int>(_start, days[i - 1]));
            _start = days[i];
        }
    }
    else
    {
        seqs.Add(new Tuple<int, int>(_start, days[i - 1]));
    }
}
var largestSeq = seqs
      .OrderByDescending(s => s.Item2 - s.Item1)
      .FirstOrDefault();

查找列表中最长的序列<；int>；

此解决方案较短，但使用了副作用，因此无法并行化：

var days = new List<int> { 1, 4, 5, 6, 7, 8, 20, 24, 25, 26, 30 };
var groupNumber = 0;
var longestGroup = days
    .Select((x, i) => new
                        {
                            Item = x,
                            Index = i
                        })
    .GroupBy(x => x.Index == 0 || x.Item - days[x.Index - 1] == 1
        ? groupNumber :
        ++groupNumber)
    .OrderByDescending(x => x.Count())
    .First()
    .Select(x => x.Item)
    .ToArray();
Console.WriteLine(longestGroup.First()+", "+longestGroup.Last());

输出：

4, 8

这个版本没有使用副作用：

var days = new List<int> { 1, 4, 5, 6, 7, 8, 20, 24, 25, 26, 30 };
var groupEnds = days
    .Select((x, i) => new
    {
        Item = x,
        Index = i
    })
    .Where(x => x.Index > 0)
    .Where(x => x.Item - days[x.Index - 1] > 1)
    .Select(x => x.Index)
    .Concat(new[]{days.Count})
    .ToArray();
var groupBounds =
    new[]{new{First=0,Last=groupEnds[0]-1}}
    .Concat(groupEnds
        .Select((x,i) => new{Item=x,Index=i})
        .Where(x => x.Index > 0)
        .Select(x => new{First=groupEnds[x.Index-1],Last=x.Item-1})
        )
    .ToArray();
var longestGroup = groupBounds
    .OrderByDescending(x => x.Last - x.First)
    .First();
Console.WriteLine(days[longestGroup.First] + ", " + days[longestGroup.Last]);

输出：

4, 8

我的版本，看起来与@Gurgadourgen的非常相似。

List<int> days = new List<int> { 1, 4, 5, 6, 7, 8, 20, 24, 25, 26, 30 };           
int longestSequenceLength = 0;
int startIndexOfLongestSequence = 0;
int currentSequenceLength = 0;
int currentStartSequenceIndex = 0;
for (int i = 0; i < days.Count; i++) {
    if (i == 0 || days[i] != days[i - 1] + 1) {
        currentSequenceLength = 1;
        currentStartSequenceIndex = i;
    }
    else {
        currentSequenceLength++;
    }
    if (currentSequenceLength > longestSequenceLength) {
        longestSequenceLength = currentSequenceLength;
        startIndexOfLongestSequence = currentStartSequenceIndex;
    }
}
Console.WriteLine(string.Join(",",days.Skip(startIndexOfLongestSequence)
   .Take(longestSequenceLength))); 

int longestSeqStart = days[0];
int longestSeqEnd = days[0];
int curSeqStart = days[0];
int curSeqEnd = days[0];
int lastVal = days[0];
for(int i = 1; i < days.Count(); i++)
{
    if(days[i] == lastVal + 1)
    {
        curSeqEnd = days[i];
        if(curSeqEnd - curSeqStart > longestSeqEnd - longestSeqStart )
        {
            longestSeqStart = curSeqStart;
            longestSeqEnd = curSeqEnd;
        }
    }
    else
    {
        curSeqStart = curSeqEnd = days[i];
    }
    lastVal = days[i];
}

我还没有测试过，但我已经盯着它看了整整五分钟，它看起来很好。我将在ideone中运行一些测试，然后回来在：P 中编辑它们

[EDIT]经过测试，它确实有效。对于整数列表，"天">

{1,2,3,4,5,12,13,14,15,16,17,18,2,3,4,5}

它吐出12-18，这是正确的答案。我会在这里发布Ideone链接。

[EDIT 2]请注意，这几乎没有经过优化，在实际代码中使用之前，可以(也应该(进一步渲染。例如，我在写下这篇文章后才意识到，实际上甚至不需要"lastVal"，因为我们只需要检查最后一个索引(I-1(中"days"的值。

这应该只是一个逻辑基础，用来解决你的问题，在这里。不是最终解决方案。

相关文章：