Python 中最長的連續序列

假設我們有一個整數陣列。我們必須找到最長連續元素序列的長度。因此，如果輸入類似於 [100, 4, 250, 1, 3, 2]，答案將為 4，因為最長的連續序列是 [1,2,3,4]。

為了解決這個問題，我們將按照以下步驟進行操作 −

• 將陣列設為 set，longest := 0

• 對於 range 陣列中的 i −

  • 如果 i – 1 不在 a 中 −

    • current := i，streak := 0

    • 當 i 在 a 中 −

      • 將 i 增加 1，將 streak 增加 1

      • longest := longest 和 streak 中的最大值

• 返回 longest

示例

讓我們看以下實現以更好地理解 −

 線上演示

class Solution(object):
   def longestConsecutive(self, a):
      a = set(a)
      longest = 0
      for i in a:
         if i-1 not in a:
            current = i
            streak = 0
            while i in a:
               i+=1
               streak+=1
               longest = max(longest,streak)
      return longest

ob = Solution()
print(ob.longestConsecutive([100,4,250,1,3,2]))

輸入

[100,4,250,1,3,2]

輸出

4

Arnab Chakraborty

更新於：2020 年 5 月 26 日

5000+ 瀏覽

重啟你的 職業

完成課程認證

開始