128. Longest Consecutive Sequence-從數組中尋找最長的連續數字

Pandaaa 發布于2019-07-30 16:09 / 2233人閱讀

摘要：描述例子要求分析從未排序的數組中尋找最長的連續的數字，必然要循環一遍所有的數字，因為連續，所以以出來的數字為基準，向左右擴散，直到沒有連續的，利用了和的特性。

描述：

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.

分析

從未排序的數組中尋找最長的連續的數字，必然要循環一遍所有的數字，因為連續，所以以pop出來的數字為基準，向左右擴散，直到沒有連續的，利用了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)

GPU云服務器云服務器數組中未出現的數字 php 數組最長尋找重復數字 c語言連續數字

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/41517.html

[Leetcode] Longest Consecutive Sequence 最長連續數列

摘要：集合法復雜度時間空間思路將所有數都加入集合中，然后再遍歷這些數，因為我們能的判斷某個數是否在集合中，所以我們可以一個個向上或者向下檢查。時間復雜度仍是，因為我們不會檢查不存在于數組的數，而存在于數組的數也只會檢查一次。 Longest Consecutive Sequence Given an unsorted array of integers, find the length o...

lei___ 2019-08-14 12:38 評論0 收藏0
[Leetcode] Binary Tree Longest Consecutive Sequenc

摘要：遞歸法復雜度時間空間思路因為要找最長的連續路徑，我們在遍歷樹的時候需要兩個信息，一是目前連起來的路徑有多長，二是目前路徑的上一個節點的值。代碼判斷當前是否連續返回當前長度，左子樹長度，和右子樹長度中較大的那個 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

xi4oh4o 2019-08-14 16:16 評論0 收藏0
[LintCode/LeetCode] Longest Consecutive Sequence

摘要：先排序，然后用數組記錄每一位上連續序列的長度，每次循環更新最大值存為。 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...

buildupchao 2019-08-14 16:25 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
298. Binary Tree Longest Consecutive Sequence

摘要：題目解答分治，一種不帶返回值，但需要用全局變量，一種帶返回值，不用全局變量有全局變量題目：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...

荊兆峰 2019-08-14 14:15 評論0 收藏0