資訊專欄INFORMATION COLUMN
摘要：描述例子要求分析從未排序的數(shù)組中尋找最長(zhǎng)的連續(xù)的數(shù)字，必然要循環(huán)一遍所有的數(shù)字，因?yàn)檫B續(xù)，所以以出來(lái)的數(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ù)組中尋找最長(zhǎng)的連續(xù)的數(shù)字，必然要循環(huán)一遍所有的數(shù)字，因?yàn)檫B續(xù)，所以以pop出來(lái)的數(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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/41517.html
摘要：集合法復(fù)雜度時(shí)間空間思路將所有數(shù)都加入集合中，然后再遍歷這些數(shù)，因?yàn)槲覀兡艿呐袛嗄硞€(gè)數(shù)是否在集合中，所以我們可以一個(gè)個(gè)向上或者向下檢查。時(shí)間復(fù)雜度仍是，因?yàn)槲覀儾粫?huì)檢查不存在于數(shù)組的數(shù)，而存在于數(shù)組的數(shù)也只會(huì)檢查一次。 Longest Consecutive Sequence Given an unsorted array of integers, find the length o...
摘要：遞歸法復(fù)雜度時(shí)間空間思路因?yàn)橐易铋L(zhǎng)的連續(xù)路徑，我們?cè)诒闅v樹(shù)的時(shí)候需要兩個(gè)信息，一是目前連起來(lái)的路徑有多長(zhǎng)，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長(zhǎng)度，左子樹(shù)長(zhǎng)度，和右子樹(shù)長(zhǎng)度中較大的那個(gè) Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...
摘要：先排序，然后用數(shù)組記錄每一位上連續(xù)序列的長(zhǎng)度，每次循環(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)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： 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...
閱讀 1881·2023-04-25 15:50
閱讀 1366·2021-09-22 15:49
閱讀 3082·2021-09-22 15:06
閱讀 3757·2019-08-30 15:54
閱讀 2394·2019-08-29 11:33
閱讀 2175·2019-08-23 17:56
閱讀 2301·2019-08-23 17:06
閱讀 1353·2019-08-23 15:55
