【題目】

　　給定無序數(shù)組，返回其中最長的連續(xù)序列的長度。

【舉例】

　　arr = [100, 4, 200, 1, 3, 2]，最長的連續(xù)序列為[1, 2, 3, 4]，所以返回4。

【基本思路】

　　利用哈希表可以實(shí)現(xiàn)時間、空間復(fù)雜度都為O(N)的方法。具體過程如下：

生成哈希表map，key表示遍歷過的某個數(shù)，value代表key這個數(shù)所在的最長連續(xù)序列的長度。

從左到右依次遍歷數(shù)組，假設(shè)遍歷到arr[i]，如果arr[i]已經(jīng)存在于map中，直接跳過，這是因?yàn)樽铋L的連續(xù)序列必定不包含相同的值。如果arr[i]不存在與map中，則將arr[i]作為key添加到map中，其value值設(shè)為1，表示目前arr[i]單獨(dú)作為一個連續(xù)序列。

之后，在map表中查找是否含有arr[i]-1，如果有，說明arr[i]-1和arr[i]可以合并，合并之后記錄新序列的長度len、最大值lmax和最小值lmin，將map表中key為lmax，lmin的value值更新為len；

同理在map表中查找是否含有arr[i]+1，如果有，說明arr[i]和arr[i] + 1可以合并，合并之后記錄新序列的長度len、最大值rmax和最小值rmin，將map表中key為rmax，rmin的value值更新為len。

遍歷過程中用全局變量max記錄每次合并出的序列的長度的最大值，最后返回max
?

def longestConsecutive(arr):if arr == None or len(arr) ==0:return 0map_ = {}maxstr = 1for i in range(len(arr)):if arr[i] not in map_:map_[arr[i]] = 1if arr[i] - 1 in map_:maxstr = max(maxstr,merge(map_,arr[i]-1,arr[i]))if arr[i] + 1 in map_:maxstr = max(maxstr,merge(map_,arr[i],arr[i]+1))return maxstrdef merge(map_,less,more):left = less - map_[less] + 1right = more + map_[more] - 1 length = right - left + 1map_[left] = lengthmap_[right] = lengthreturn length

?

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的数组中最长连续序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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