pen22

LeetCode - 128.最长连续序列

发表于 分类于 阅读次数： Valine：

题面

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

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

样例

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

思路

要求时间复杂度为 $O(n)$ 自然是不能排序了，并查集可以把属性相似的一类数聚在一起的作用，而且压缩后的并查集时间复杂度也很可观。

  • 先初始化数组中每一个数指向本身。

  • 循环数组

    • 如果 $nums[i] + 1$ 在并查集中， $nums[i] + 1$ 指向 $nums[i]$。

    • 如果 $nums[i] - 1$ 在并查集中， $nums[i]$ 指向 $nums[i] - 1$。

⚠这题依然有个空数组问题，又被坑了。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unordered_map<int, int> p;
int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}
int longestConsecutive(vector<int>& nums) {
    int n = nums.size(); if(n == 0) return 0;
    for(int item : nums) { p[item] = item; }
    for(int item : nums) {
        if(p.count(item + 1)) p[item + 1] = item;
        if(p.count(item - 1)) p[item] = item - 1;
    }
    int ans = 0;
    for(int item : nums) {
        int temp = find(item);
        ans = max(ans, item - temp);
    }
    return ans + 1;
}