leetcode128-最长连续序列

原题

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2] 输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解法

思想

哈希集,先遍历一遍存储每个数字是否出现过,第二遍遍历找到一个连续序列的头(没有等于这个值-1的元素)计算这个连续序列的长度,并存储下最大值

代码

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        int maxLen = 0;
        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int curNum = num;
                int curLen = 1;
                while (set.contains(curNum + 1)) {
                    curNum += 1;
                    curLen += 1;
                }
                maxLen = Math.max(maxLen,curLen);
            }
        }
        return maxLen;
    }
}
func longestConsecutive(nums []int) int {
    numMap := map[int]bool{}
    for _, num := range nums{
        numMap[num] = true
    }

    ans := 0
    for _, num := range nums{
        // 只遍历一个连续序列的头
        if !numMap[num-1]{
            cur := 1
            temp := num
            for numMap[temp+1]{
                cur ++
                temp ++
            }
            ans = max(ans, cur)
        }
    }
    return ans
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode128-%e6%9c%80%e9%95%bf%e8%bf%9e%e7%bb%ad%e5%ba%8f%e5%88%97/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月5日
下一篇 2020年6月7日

相关推荐

  • 二叉树中序遍历-折纸问题

    原题(来源牛客网) 请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展开。此时有1条折痕,突起的⽅向指向纸条的背⾯,这条折痕叫做“下”折痕 ;突起的⽅向指向纸条正⾯…

    2020年4月27日
    02690
  • leetcode99-恢复二叉搜索树

    原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1 …

    算法 2020年3月1日
    080
  • leetcode242-有效的字母异位词

    原题 https://leetcode.cn/problems/valid-anagram/description/ 解法 (针对进阶场景,若字符串中存在unicode字符) fu…

    算法 2024年3月26日
    050
  • leetcode162-寻找峰值

    原题 峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。 数组可能包含多个峰值,在这种情况…

    算法 2020年1月3日
    060
  • leetcode138-复制带随机指针的链表

    这道题和leetcode133-克隆图有异曲同工之妙。 原题 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。…

    2019年12月17日
    0330
  • leetcode238-除自身以外数组的乘积

    原题 给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积…

    算法 2020年6月4日
    080
  • leetcode146-LRU缓存机制

    原题 运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) -…

    算法 2020年5月25日
    0100
  • leetcode68-文本左右对齐

    原题 https://leetcode.cn/problems/text-justification/description 解法 贪心即可 func fullJustify(wo…

    算法 2024年3月23日
    0110
  • leetcode410-分割数组的最大值

    原题 给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意:数组长度 n 满足以下条件: 1…

    算法 2020年1月9日
    0690
  • leetcode1-两数之和

    原题 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能…

    算法 2019年12月20日
    0110

发表回复

登录后才能评论