`
blue2048
  • 浏览: 182774 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

[leetcode]Longest Consecutive Sequence - o(N) java

阅读更多
package leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * User: FR
 * Time: 1/4/15 6:01 PM
 *
 * 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.
 */
public class LongestConsecutiveSequence {
    public int longestConsecutive(int[] num) {
        int maxCounter=0;
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        for(int n : num){
            if(map.containsKey(n))
                continue;
            int[] array = new int[2];
            array[0]=n;
            array[1]=n;
            map.put(n, array);
        }
        for(int n : map.keySet()){
            if(map.containsKey(n-1)){
                map.get(n)[0] = map.get(n-1)[0];
            }
            if(map.containsKey(n+1)){
                map.get(n)[1] = map.get(n+1)[1];
            }
            if((map.get(n)[1] - map.get(n)[0]+1)> maxCounter){
                maxCounter = map.get(n)[1] - map.get(n)[0]+1;
            }
            map.get(map.get(n)[0])[1]=map.get(n)[1];
            map.get(map.get(n)[1])[0]=map.get(n)[0];
        }
        return maxCounter;
    }

    public static void main(String[] args){
        int[] a = {-3,2,8,5,1,7,-8,2,-8,-4,-1,6,-6,9,6,0,-7,4,5,-4,8,2,0,-2,-6,9,-4,-1};
        LongestConsecutiveSequence l = new LongestConsecutiveSequence();
        System.out.println(l.longestConsecutive(a));
    }
}

 

分享到:
评论

相关推荐

    js-leetcode题解之128-longest-consecutive-sequence.js

    javascript js_leetcode题解之128-longest-consecutive-sequence.js

    python-leetcode题解之128-Longest-Consecutive-Sequence

    python python_leetcode题解之128_Longest_Consecutive_Sequence

    leetcode正方体堆叠-TakeUforward-SDE_180:TakeUforward-SDE_180

    leetcode正方体收藏TakeUforward-SDE_180 要了解整个列表和其他内容,如项目、简历、如何进行面试……观看整个视频: 在以下位置找到展示位置系列: 第一天:(数组) 在 N+1 整数数组中查找重复项。 (描述中的问题...

    LeetCode最全代码

    | _O(n)_ ~ _O(n^2)_ | _O(n)_ | Medium || Bit Manipulation, Counting Sort, Pruning| 342 | [Power of Four](https://leetcode.com/problems/power-of-four/) | [C++](./C++/power-of-four.cpp) [Python](./...

    leetcode题库-leetcode:算法代码-JavaScript

    例如,"最长连续序列"(Longest Consecutive Sequence)题目的解决方案通常会用到哈希表来存储数组元素及其出现的次数,再结合深度优先搜索或广度优先搜索策略找出最长的连续序列。 3. 优化技巧:在解决LeetCode...

    LeetCode题解(java语言实现).pdf

    * Longest Consecutive Sequence Java:该题目要求找到最长的连续序列,实现方法使用了哈希表和迭代算法。 * Search a 2D Matrix:该题目要求在二维矩阵中查找元素,实现方法使用了二分查找算法。 * Rotate Image:...

    leetcode卡-LeetCode-HashTable:此存储库包含HashTable探索卡中所有问题的解决方案

    5. **滑动窗口最大值/最小值**:例如“数组中的最长连续序列”(Longest Consecutive Sequence),哈希表可以帮助我们快速查询元素及其相邻元素的状态,从而找到最长连续序列。 6. **统计问题**:如“数组中出现...

    lrucacheleetcode-leetcode:个人刷leetcode遇到的一些题汇总(golang)

    longest-consecutive-sequence max-area-of-island next-greater-element-ii serialize-and-deserialize-binary-tree subarray-sum-equals-k binary-tree-preorder-traversal n-queens-ii populating-next-right-...

    leetcode分类-Leetcode:Leetcode题解

    leetcode 分类 Leetcode代码题解 随缘刷题,选择性更新题解 LeetCode 94 144 145 ...longest-consecutive-sequence 最长连续序列: Leetcode 155 Min Stack 最小栈: LeetCode 773 滑动谜题: ......

    leetcode-cpp刷题

    - **2.1.6 Longest Consecutive Sequence** - 找出数组中最长的连续子序列。 - 实现思路:可以使用哈希表存储每个元素及其连续状态,然后遍历数组找到最长的连续序列。 - **2.1.7 Two Sum** - 寻找数组中两个数...

    leetcode-java:leetcode在线判断的Java解决方案

    2. "最长连续序列"(Longest Consecutive Sequence):利用HashSet存储数值并更新最长连续序列长度。 这些案例展示了如何将数据结构和算法应用到实际问题中,帮助我们更好地理解和实践Java在LeetCode中的解题策略。...

    leetcode中文版

    2. **2.1.6 Longest Consecutive Sequence**:给定一个未排序的整数数组,找出其中最长连续序列的长度。 3. **2.1.7 Two Sum**:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个...

    leetcode跳跃-leetcode:leetcode题解

    比如,“最长连续序列”(Longest Consecutive Sequence)要求找到给定无序整数数组中最长的连续序列长度,这涉及到哈希表和递归/迭代的巧妙结合。 LeetCode平台的开源特性意味着用户可以查看其他人的解决方案,...

    LeetCode刷题题解答案(c++).pdf 彻底搞懂了编程算法题,成功拿到了大厂offer!

    4. **最长连续序列(Longest Consecutive Sequence)** - **问题描述**:给定一个未排序的整数数组,找出最长连续序列的长度。 - **解决方案**: - 使用哈希集合存储数组中的所有元素。 - 遍历数组中的每个元素...

    leetcode答案-leetcode:leetcode上的算法答案

    如“最长连续序列”(Longest Consecutive Sequence)问题,可以使用动态规划在O(n)时间复杂度内找到答案。 9. **分治策略**:将大问题分解为小问题,逐个解决后再合并结果。如“归并排序”(Merge Sort),通过...

    leetcode添加元素使和等于-leetcode:leetcode

    Longest_Consecutive_Sequence 双向确认是否连续,避免重复的n^2复杂度 Palindrome_Partitioning DP,避免递归调用,利用数组储存已算出来的数值,由后向前逐渐增加字符串处理 Palindrome_Partitioning_2 同上 Sum_...

    lrucacheleetcode-LeetCode:这个库用于总结leetcode中遇到的习题,期望按照数据结构和常用方法分成2类,进行总结,

    Consecutive Sequence 7 Two Sum Hash,夹逼均可 8 3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next Permutation 公式 13 Permutation Sequence 公式 14 Valid ...

    python-leetcode面试题解之第128题最长连续序列-题解.zip

    LeetCode的第128题,名为"Longest Consecutive Sequence",要求找到给定无序整数数组中,最长的连续整数序列的长度。例如,对于输入数组 [100, 4, 200, 1, 3, 2],最长连续序列是 [1, 2, 3, 4],其长度为4。 首先,...

    leetcode分类-leetcode:leetcode刷题

    4. **滑动窗口**:在数组中使用滑动窗口进行统计,如“最长连续序列”(Longest Consecutive Sequence)。 5. **数组分割**:根据特定条件将数组分割成多个子数组,如“分割数组的最大和”(MaxChunks ToSorted)。...

Global site tag (gtag.js) - Google Analytics