[Leetcode] Longest Consecutive Sequence 最長連續(xù)數(shù)列

lei___ 發(fā)布于2019-08-14 12:38 / 1783人閱讀

摘要：集合法復雜度時間空間思路將所有數(shù)都加入集合中，然后再遍歷這些數(shù)，因為我們能的判斷某個數(shù)是否在集合中，所以我們可以一個個向上或者向下檢查。時間復雜度仍是，因為我們不會檢查不存在于數(shù)組的數(shù)，而存在于數(shù)組的數(shù)也只會檢查一次。

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, 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.

排序法 復雜度

時間 O(NlogN) 空間 O(1)

思路

將數(shù)組排序后，從前向后遍歷，找到最長的連續(xù)部分，該方法隨不符合題意，但是不用空間。

集合法 復雜度

時間 O(N) 空間 O(N)

思路

將所有數(shù)都加入集合中，然后再遍歷這些數(shù)，因為我們能O(1)的判斷某個數(shù)是否在集合中，所以我們可以一個個向上或者向下檢查。為了避免之后重復檢查，我們每查到一個數(shù)，都要將其從集合中移除。這樣每遇到一個數(shù)，都檢查它的上下邊界，就能找出最長的連續(xù)數(shù)列。時間復雜度仍是O(N)，因為我們不會檢查不存在于數(shù)組的數(shù)，而存在于數(shù)組的數(shù)也只會檢查一次。

代碼

public class Solution {
    public int longestConsecutive(int[] nums) {
        int maxlen = 0;
        Set set = new HashSet();
        // 先將所有數(shù)字加入數(shù)組中
        for(int n : nums){
            set.add(n);
        }
        // 對于每個數(shù)我們都在集合中一一檢查它的上下邊界
        for(int n : nums){
            // 暫存n，供檢查下邊界時使用
            int curr = n, len = 0;
            // 一個一個檢查上邊界
            while(set.contains(curr)){
                curr++;
                len++;
                set.remove(curr);
            }
            // 一個一個檢查下邊界
            curr = n - 1;
            while(set.contains(curr)){
                curr--;
                len++;
                set.remove(curr);
            }
            maxlen = Math.max(len, maxlen);
        }
        return maxlen;
    }
}

云服務器 GPU云服務器 Longest Sequence Consecutive LeetCode

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/64610.html

[Leetcode] Binary Tree Longest Consecutive Sequenc

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

xi4oh4o 2019-08-14 16:16 評論0 收藏0
128. Longest Consecutive Sequence-從數(shù)組中尋找最長的連續(xù)數(shù)字

摘要：描述例子要求分析從未排序的數(shù)組中尋找最長的連續(xù)的數(shù)字，必然要循環(huán)一遍所有的數(shù)字，因為連續(xù)，所以以出來的數(shù)字為基準，向左右擴散，直到?jīng)]有連續(xù)的，利用了和的特性。描述： Given an unsorted array of integers, find the length of the longest consecutive elements sequence. 例子： Given ...

Pandaaa 2019-07-30 16:09 評論0 收藏0
[LintCode/LeetCode] Longest Consecutive Sequence

摘要：先排序，然后用數(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...

buildupchao 2019-08-14 16:25 評論0 收藏0
[LeetCode] 549. Binary Tree Longest Consecutive Se

Problem Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree. Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] ...

bingchen 2019-08-19 11:11 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0