[LintCode/LeetCode] Longest Consecutive Sequence

buildupchao 發(fā)布于2019-08-14 16:25 / 992人閱讀

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

Example

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Note

先排序，然后用count[]數(shù)組記錄每一位上連續(xù)序列的長(zhǎng)度，每次循環(huán)更新最大值存為max。

Solution

public class Solution {
    public int longestConsecutive(int[] num) {
        Arrays.sort(num);
        int[] count = new int[num.length];
        count[0] = 1;
        int max = 1;
        for (int i = 1; i < num.length; i++) {
            if (num[i] == num[i-1]) count[i] = count[i-1];
            else if (num[i] == num[i-1]+1) count[i] = count[i-1]+1;
            else count[i] = 1;
            max = Math.max(max, count[i]);
        }
        return max;
    }
}

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

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

相關(guān)文章

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 評(píng)論0 收藏0
[Leetcode] Binary Tree Longest Consecutive Sequenc

摘要：遞歸法復(fù)雜度時(shí)間空間思路因?yàn)橐易铋L(zhǎng)的連續(xù)路徑，我們?cè)诒闅v樹的時(shí)候需要兩個(gè)信息，一是目前連起來(lái)的路徑有多長(zhǎng)，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長(zhǎng)度，左子樹長(zhǎng)度，和右子樹長(zhǎng)度中較大的那個(gè) Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

xi4oh4o 2019-08-14 16:16 評(píng)論0 收藏0
[Leetcode] Longest Consecutive Sequence 最長(zhǎng)連續(xù)數(shù)列

摘要：集合法復(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...

lei___ 2019-08-14 12:38 評(píng)論0 收藏0
128. Longest Consecutive Sequence-從數(shù)組中尋找最長(zhǎng)的連續(xù)數(shù)字

摘要：描述例子要求分析從未排序的數(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 ...

Pandaaa 2019-07-30 16:09 評(píng)論0 收藏0
Binary Tree Longest Consecutive Sequence

摘要：題目鏈接這一個(gè)類型的題都一樣用，分治的思想。兩種方式一種用，另一種直接把的長(zhǎng)度作為返回值，思路都一樣。也可以解，用或者來(lái)做，但是本質(zhì)都是。用用返回值在當(dāng)前層處理分別處理左右節(jié)點(diǎn)，這樣不用傳上一次的值，注意這樣初始的就是了 Binary Tree Longest Consecutive Sequence 題目鏈接：https://leetcode.com/problems... 這一個(gè)類...

svtter 2019-08-14 17:19 評(píng)論0 收藏0