在列表<int>

Question

我有以下列表中找到最長的序列：

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(); 

Answer 1

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

[編輯]測試它，它確實有效。對於整數列表，「天」

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

它吐出12-18，這是正確的答案。 我只會發布Ideone link here。

[編輯2]請注意，這是幾乎沒有優化，並可以（並應該）進一步降低之前使用實際的代碼。例如，我在寫完這篇文章後才意識到「lastVal」實際上並不是必需的，因爲我們可以在最後一個索引（i-1）處檢查「days」的值。

這隻能作爲解決您遇到的問題的邏輯基礎。不是最終的解決方案。

Answer 2

我的版本看起來很像@Gurgadurgen的版本。

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))); 

Answer 3

該溶液是較短，但使用的副作用，所以它不能並行：

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