[LintCode/LeetCode] Longest Consecutive Sequence

buildupchao 发布于2019-08-14 16:25 / 666人阅读

摘要：先排序，然后用数组记录每一位上连续序列的长度，每次循环更新最大值存为。

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[]数组记录每一位上连续序列的长度，每次循环更新最大值存为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;
    }
}

服务器托管云服务器 Longest Sequence Consecutive

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66203.html

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
[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
[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
128. Longest Consecutive Sequence-从数组中寻找最长的连续数字

摘要：描述例子要求分析从未排序的数组中寻找最长的连续的数字，必然要循环一遍所有的数字，因为连续，所以以出来的数字为基准，向左右扩散，直到没有连续的，利用了和的特性。描述： Given an unsorted array of integers, find the length of the longest consecutive elements sequence. 例子： Given ...

Pandaaa 2019-07-30 16:09 评论0 收藏0
Binary Tree Longest Consecutive Sequence

摘要：题目链接这一个类型的题都一样用，分治的思想。两种方式一种用，另一种直接把的长度作为返回值，思路都一样。也可以解，用或者来做，但是本质都是。用用返回值在当前层处理分别处理左右节点，这样不用传上一次的值，注意这样初始的就是了 Binary Tree Longest Consecutive Sequence 题目链接：https://leetcode.com/problems... 这一个类...

svtter 2019-08-14 17:19 评论0 收藏0