Title

給定一個未排序的整數(shù)數(shù)組，找出最長連續(xù)序列的長度。

要求算法的時間復雜度為 O(n)。

示例:

輸入: [100, 4, 200, 1, 3, 2]
輸出: 4
解釋: 最長連續(xù)序列是 [1, 2, 3, 4]。它的長度為 4。

Solve

暴力

沒想到啊，暴力的方法竟然能AC，直接排序，然后遍歷整個序列，判斷當前項與前一項的差，為0則continue，為1則+1，其它情況更新ans。

class Solution:def longestConsecutive(self, nums: List[int]) -> int:if not nums:return 0nums.sort()ans, temp = 0, 0for index in range(1, len(nums)):if nums[index] - nums[index - 1] == 1:temp += 1elif nums[index] - nums[index - 1] == 0:continueelse:ans = max(ans, temp)temp = 0ans = max(ans, temp)return ans + 1

哈希表：

考慮枚舉數(shù)組中的每個數(shù) x，考慮以其為起點，不斷嘗試匹配 x+1, x+2, ? 是否存在，假設最長匹配到了 x+y，那么以 x 為起點的最長連續(xù)序列即為 x, x+1, x+2, ?,x+y，其長度為 y+1。

但仔細分析這個過程，我們會發(fā)現(xiàn)其中執(zhí)行了很多不必要的枚舉，如果已知有一個 x, x+1, x+2,?,x+y 的連續(xù)序列，而我們卻重新從 x+1，x+2 或者是 x+y 處開始嘗試匹配，那么得到的結果肯定不會優(yōu)于枚舉 x 為起點的答案，因此我們在外層循環(huán)的時候碰到這種情況跳過即可。

那么怎么判斷是否跳過呢？由于我們要枚舉的數(shù) x 一定是在數(shù)組中不存在前驅(qū)數(shù) x-1 的，不然按照上面的分析我們會從 x-1 開始嘗試匹配，因此我們每次在哈希表中檢查是否存在 x-1 即能判斷是否需要跳過了。

復雜度分析

時間復雜度：O(n)，其中 n 為數(shù)組的長度。具體分析已在上面正文中給出。

空間復雜度：O(n)。哈希表存儲數(shù)組中所有的數(shù)需要 O(n) 的空間。

class Solution:def longestConsecutive(self, nums):longest_streak = 0num_set = set(nums)for num in num_set:if num - 1 not in num_set:current_num = numcurrent_streak = 1while current_num + 1 in num_set:current_num += 1current_streak += 1longest_streak = max(longest_streak, current_streak)return longest_streak

總結

以上是生活随笔為你收集整理的128. Longest Consecutive Sequence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。