LeetCode第128题:最长连续序列
给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 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;
}
执行结果
0条评论