[Leetcode]128. Longest Consecutive Sequence

2023/11/30閱讀時間約 2 分鐘

題目 : 128. Longest Consecutive Sequence Medium

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.


Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9


1.

numSet : 用set()函數將nums做成集合,去除重複的數字

longest : 紀錄目前最大長度

length : 記錄由num開始算連續數字的長度


line 8 : 先看num是不是連續整數中的最小數,如果是就開始往後找num+1、num+2....

直到找到連續整數的最大長度

line 12 : 跳出迴圈後查看紀錄的length和longest那個最大,用max()回傳最大長度

class Solution:
def longestConsecutive(self, nums: List[int]) -> int:

numSet = set(nums)
longest = 0

for num in nums :
if num-1 not in numSet:
length = 0
while (num+length) in numSet:
length += 1
longest = max(length,longest)

return longest



7會員
36內容數
這裡會放一些我寫過的 Leetcode 解題和學習新技術的筆記
留言0
查看全部
發表第一個留言支持創作者!