LeetCode.M128.最长连续序列

LeetCode.M128.最长连续序列

题目：

题目大意：

如图所示。

数据范围：

如图所示
1

---

一 、解法 ：

思路：

并查集 + 哈希：在使用并查集记录一个连续序列(的下标)时，维护连续序列的长度。思路与[AcWing837连通块中点的数量]大致一致。都是维护数量信息。使用哈希表记录值对应的下标。

具体做法：第一次遍历到一个数 x 时，将 加到 map 中，如果 x - 1 已经遍历过了，则用并查集合并 x 和 x - 1 这两个数的下标，代表在该下标的数是一个连续的序列，同时更新数量信息。对 x + 1 同理。

​

代码：

class Solution {
    public int[] p = new int[100010];
    public int[] size = new int[100010];

    public int find(int x){
        if (x != p[x]){
            p[x] = find(p[x]);
        }
        return p[x];
    }

    public  void union(int a, int b){
        int pa = find(a), pb = find(b);
        p[pa] = pb;
        size[pb] += size[pa];
    }

    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> indexV = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i ++ ){
            p[i] = i;
            size[i] = 1;
        }
        for (int i = 0; i < n; i ++ ){
            if (!indexV.containsKey(nums[i])){
                indexV.put(nums[i], i);
                if (indexV.containsKey(nums[i] - 1)){
                    union(i, indexV.get(nums[i] - 1));
                }
                if (indexV.containsKey(nums[i] + 1)){
                    union(indexV.get(nums[i] + 1), i);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i ++ ){
            if (i == p[i]){
                ans = Math.max(ans, size[i]);
            }
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

时空复杂度分析等：

• 时间复杂度 : O(n)
• 空间复杂度 : O(n)

---

二 、解法 ：

思路：

集合：先将所有元素插入 set 中，然后遍历所有元素，遍历到 x 时，如果没有比 x 小的 x - 1，即 x 为这一个序列的第一个元素时（保证不会从 x + 1 再次查找该序列以降低时间复杂度），不断地在 set 中查找 x + 1、x + 2 … ，则找到了以 x 为第一个元素的序列，再更新最大序列长度

代码：

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i ++ ){
            set.add(nums[i]);
        }
        int ans = 0;
        for (int i = 0; i < nums.length; i ++ ){
            if (!set.contains(nums[i] - 1)){
                int len = 0, k = nums[i];
                while (set.contains(k)){
                    k ++ ;
                    len ++ ;
                }
                ans = Math.max(ans, len);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时空复杂度分析等：

• 时间复杂度 : O(n)
• 空间复杂度 : O(n)

---

三 、解法 ：

思路：

哈希：使用一个哈希表，在一个序列的左右端点处记录该序列的长度。

• 若数已在哈希表中：跳过不做处理
• 若是新数加入：
  • 取出其左右相邻数已有的连续区间长度 left 和 right
  • 计算当前数的区间长度为：len = left + right + 1
  • 根据 len 更新最大长度 ans 的值
  • 更新区间两端点的长度值

代码：

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < nums.length; i ++ ){
            if (!map.containsKey(nums[i])){
                int left = map.getOrDefault(nums[i] - 1, 0);
                int right = map.getOrDefault(nums[i] + 1, 0);
                int len = left + right + 1;
                ans = Math.max(ans, len);
                map.put(nums[i],len);
                map.put(nums[i] - left, len);
                map.put(nums[i] + right, len);
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时空复杂度分析等：

• 时间复杂度 : O(n)

• 空间复杂度 : O(n)

题目链接：

128. 最长连续序列 - 力扣（LeetCode）