题目描述
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
题意:给定一个未排序的整数数组,找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。
算法1
(并查集)
题解2:并查集。我们可以将数组中数值相邻的元素使用并查集合并,最后看一下哪一个连通块最大,我们就可以求出所需要的答案了。在使用并查集时,额外需要注意的一点就是,可能会有重复元素,所以我们先使用set求出所有的不重复元素,对这些不重复的元素进行并查集操作。我们使用了一个map来存储数值和数组下标的映射。
C++ 代码
class Solution {
public:
vector<int> fa,size;
int getfa(int x)
{
if(x != fa[x]) fa[x] = getfa(fa[x]);
return fa[x];
}
void uni(int x, int y)
{
int fx = getfa(x),fy = getfa(y);
if(fx != fy)
{
if(size[fx] < size[fy])
{
fa[fx] = fy;
size[fy] += size[fx];
}else
{
fa[fy] = fx;
size[fx] += size[fy];
}
}
}
int longestConsecutive(vector<int>& nums) {
int n = nums.size(),res = 0,i = 0;
unordered_set<int> _set;
unordered_map<int,int> hash;
for(int i = 0 ; i < n ; i ++) _set.insert(nums[i]);
n = _set.size();
vector<int> arr(n,0);
for(auto x : _set) arr[i ++] = x;
fa = vector<int>(n,0),size = vector<int>(n,1);
for(int i = 0 ; i < n ; i ++)
{
fa[i] = i;
hash[arr[i]] = i;
}
for(int i = 0 ; i < n ; i ++)
{
if(hash.find(arr[i] + 1) != hash.end())
uni(i,hash[arr[i] + 1]);
if(hash.find(arr[i] - 1) != hash.end())
uni(i,hash[arr[i] - 1]);
}
for(int i = 0 ; i < n ; i ++)
if(getfa(i) == i) res = max(res,size[i]);
return res;
}
};
算法2
(哈希)
题解3:我们使用一个哈希表来存储每个数字当前最长连续序列长度。如果当前数字x
已经遇到过了,就直接跳过。否则,看一下x - 1
最长连续序列长度和x + 1
最长连续序列长度,那么当前数字x
所在的最长连续序列长度就是两者之和加上1。如果能够合并的话,不要忘记更新新的区间两个端点的哈希值。
C++ 代码
int longestConsecutive(vector<int>& nums) {
unordered_map<int,int> hash;
int res = 0;
for(auto x:nums)
{
if(hash.find(x) != hash.end()) continue;
int left = 0 ,right = 0;
if(hash.find(x - 1) != hash.end()) left = hash[x - 1];
if(hash.find(x + 1) != hash.end()) right = hash[x + 1];
if(left != 0 && right != 0)
{
hash[x - left] = left + right + 1;
hash[x + right] = left + right + 1;
}else if(left != 0)
hash[x - left] = left + 1;
else if(right != 0)
hash[x + right] = right + 1;
hash[x] = left + right + 1;
res = max(hash[x],res);
}
return res;
}
你好! 能解释下hash[x - left] ,hash[x + right] 什么意思吗?
left代表的是以x - 1为右端点的最长区间,right代表的是以x +1为左端点的区间长度,hash[x - left]代表区间合并后,我们需要更新以x - left为左端点的最长区间长度