LeetCode第128题:最长连续序列

作者 the7
发布于 2020年03月05日
评论 0
浏览 127

给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4

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

原文链接: https://leetcode-cn.com/problems/longest-consecutive-sequence/

解题

  • 用一个字典存数组中每个数字的当前连续最长长度
  • 如果已经遍历过的则跳过
  • 若从未遍历过
    • 取左右相邻的数字
    • 当前最大即为 左边存的值 + 右边存的值 + 1
    • 更新两端的值(因为在循环中只会用到两端的值)
static int LongestConsecutive(int[] nums)
{
    if (nums.Length <= 1) return nums.Length;
    var dict = new Dictionary<int,int>();
    var max = 1;
    for (var i = 0; i < nums.Length; i++)
    {
        var num = nums[i];
        if (!dict.ContainsKey(num))
        {
            var left = num - 1;
            var leftValue = 0;
            
            var right = num + 1;
            var rightValue = 0;
            
            if (dict.ContainsKey(left)) //取左侧存值
                leftValue = dict[left];
            
            if (dict.ContainsKey(right)) //取右侧存值
                rightValue = dict[right];

            var value = leftValue + rightValue + 1;
            if (value > max) max = value;
            dict[num] = value;
            if (leftValue>0)
                dict[num-leftValue]=value; //更新最左端的值
            if (rightValue>0)
                dict[num+rightValue] = value; //更新最右段的值
        }
    }
	return max;
}

执行结果

4条评论

  • 念往昔丶繁华竞逐

    2019年5月20日

    最后一个五官很漂亮,虽然脸稍微大了一点点,但也算普通人里漂亮的
  • Eleven

    2019年5月20日

    念往昔丶繁华竞逐:
    最后一个五官很漂亮,虽然脸稍微大了一点点,但也算普通人里漂亮的...
    这帖子真的是精品。美中不足的是,为什么要用繁体,虽然能看懂,但有些麻烦呀。
  • SukiU

    2019年5月20日

    我曾在某外企互联网公司工作过一段时间,他们就是那种工作时间聊天摸鱼,下班时间拼命工作,然后加班蹭加班费和补贴😂
微信公众号
站长帮
微信公众号,每日更新!