資訊專欄INFORMATION COLUMN
摘要：描述例子要求分析從未排序的數(shù)組中尋找最長的連續(xù)的數(shù)字，必然要循環(huán)一遍所有的數(shù)字，因為連續(xù)，所以以出來的數(shù)字為基準(zhǔn)，向左右擴(kuò)散，直到?jīng)]有連續(xù)的，利用了和的特性。
描述：
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
例子：
Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
要求：
Your algorithm should run in O(n) complexity.
分析
從未排序的數(shù)組中尋找最長的連續(xù)的數(shù)字，必然要循環(huán)一遍所有的數(shù)字，因為連續(xù)，所以以pop出來的數(shù)字為基準(zhǔn)，向左右擴(kuò)散，直到?jīng)]有連續(xù)的，利用了pop和in的特性。
代碼：
class Solution:
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
final_length=0
num_dict=dict()
maxlen_cur=0
while nums:
m=n=nums.pop()
maxlen_cur=1
while m-1 in nums:
nums.remove(m-1)
maxlen_cur+=1
# m-=1
m-=1
while n+1 in nums:
nums.remove(n+1)
maxlen_cur+=1
n+=1
final_length=max(maxlen_cur,final_length)
return final_length
if __name__=="__main__":
a=[100, 4, 200, 1, 3, 2]
st=Solution()
out=st.longestConsecutive(a)
print(out)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/41517.html
摘要：集合法復(fù)雜度時間空間思路將所有數(shù)都加入集合中，然后再遍歷這些數(shù)，因為我們能的判斷某個數(shù)是否在集合中，所以我們可以一個個向上或者向下檢查。時間復(fù)雜度仍是，因為我們不會檢查不存在于數(shù)組的數(shù)，而存在于數(shù)組的數(shù)也只會檢查一次。 Longest Consecutive Sequence Given an unsorted array of integers, find the length o...
摘要：遞歸法復(fù)雜度時間空間思路因為要找最長的連續(xù)路徑，我們在遍歷樹的時候需要兩個信息，一是目前連起來的路徑有多長，二是目前路徑的上一個節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長度，左子樹長度，和右子樹長度中較大的那個 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...
摘要：先排序，然后用數(shù)組記錄每一位上連續(xù)序列的長度，每次循環(huán)更新最大值存為。 Problem Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Clarification Your algorithm should run in O(n) com...
摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：題目解答分治，一種不帶返回值，但需要用全局變量，一種帶返回值，不用全局變量有全局變量 題目：Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to a...
閱讀 1878·2023-04-25 15:50
閱讀 1362·2021-09-22 15:49
閱讀 3080·2021-09-22 15:06
閱讀 3752·2019-08-30 15:54
閱讀 2392·2019-08-29 11:33
閱讀 2174·2019-08-23 17:56
閱讀 2295·2019-08-23 17:06
閱讀 1351·2019-08-23 15:55
