题目:128.最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
- 示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。- 示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9- 提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9思路1
要找到数字连续的最长序列，可以使用哈希集（HashSet）来实现 O(n) 时间复杂度的算法。具体思路如下：
- 将数组中的所有元素存入一个哈希集，以便可以在
O(1)时间内判断某个元素是否存在。 - 遍历数组中的每个元素，尝试找到该元素作为序列起点的最长连续序列。
- 对于每个元素，如果它是某个序列的起点（即当前元素减一不存在于哈希集中），则从该元素开始，逐个检查后续元素是否存在于哈希集中，计算连续序列的长度。
- 在遍历过程中，保持并更新最长序列的长度。
- 时间复杂度:O(n)
- 空间复杂度:O(n)
代码
public int longestConsecutive(int[] nums) {
int maxLen = 0;
Set<Integer> numsSet = new HashSet<>();
// 将所有元素存入哈希集
for (int num : nums) {
numsSet.add(num);
}
// 遍历每个元素，尝试找到最长连续序列
for (int num : nums) {
int currentNum;
// 判断当前元素是否是某个序列的起点
if (!numsSet.contains(num - 1)) {
currentNum = num;
// 检查后续元素是否存在于哈希集中
while (numsSet.contains(currentNum + 1)) {
currentNum += 1;
}
// 更新最长序列的长度
maxLen = Math.max(currentNum - num + 1, maxLen);
}
}
return maxLen;
}思路2
通过将每个数与其相邻的数（即比它大一和小一的数）进行合并，可以逐步形成完整的连续序列，从而最终能够找到最长的连续序列。
- 初始化并查集：为数组中的每个元素创建一个独立的集合。
- 合并相邻的元素：遍历数组中的每个元素。对每个元素
num，如果num - 1存在于数组中，则将num和num - 1合并。 - 计算集合大小：遍历数组中的每个元素，找到其所在集合的大小，记录最大值。
- 合并
num-1的意义：合并num-1是为了确保每个元素都与其相邻元素连接，从而形成连续的序列。例如，对于序列[1, 2, 3, 4]，通过将1与2合并，2与3合并，3与4合并，最终这些元素都在同一个集合中。通过这种方式，可以形成连续序列，并找到最长的连续序列长度。
- 时间复杂度:O(n)
- 空间复杂度:O(n)
代码
public class UnionFind<T> {
// parent存储每个元素的父节点，rank存储每个元素的秩（树的高度）
Map<T, T> parent;
Map<T, Integer> rank;
Map<T, Integer> size;
// 构造函数，初始化parent和rank
UnionFind() {
parent = new HashMap<>();
rank = new HashMap<>();
size = new HashMap<>();
}
// 添加新元素，初始化其父节点为自己，秩为1
void add(T item) {
if (!parent.containsKey(item)) {
parent.put(item, item);
rank.put(item, 1);
size.put(item, 1);
}
}
// 查找元素所属集合的代表元素（根节点），并进行路径压缩
T find(T item) {
if (!parent.containsKey(item)) {
throw new IllegalArgumentException("Item not found");
}
// 如果当前元素不是其自己的父节点，递归查找其父节点，并进行路径压缩
if (!parent.get(item).equals(item)) {
parent.put(item, find(parent.get(item)));
}
return parent.get(item);
} // 获取集合的大小
// 合并两个元素所在的集合，使用按秩合并
void union(T item1, T item2) {
T root1 = find(item1);
T root2 = find(item2);
// 如果两个元素的根节点不同，进行合并
if (!root1.equals(root2)) {
int rank1 = rank.get(root1);
int rank2 = rank.get(root2);
int sizeSum = size.get(root1) + size.get(root2);
// 按秩合并，将秩小的树连接到秩大的树上，更新集合的大小
if (rank1 > rank2) {
parent.put(root2, root1);
size.put(root1, sizeSum);
} else if (rank1 < rank2) {
parent.put(root1, root2);
size.put(root2, sizeSum);
} else {
parent.put(root2, root1);
size.put(root1, sizeSum);
rank.put(root1, rank1 + 1);
}
}
}
}
class Solution {
public int longestConsecutive(int[] nums) {
int maxLen = 0;
UnionFind<Integer> uf = new UnionFind<>();
// 初始化并查集
for (int num : nums) {
uf.add(num);
}
// 合并相邻的元素
for (int num : nums) {
if (uf.parent.containsKey(num - 1)) {
uf.union(num - 1, num);
}
}
// 找到最大的集合大小
for (int num : nums) {
maxLen = Math.max(maxLen, uf.size.get(num));
}
return maxLen;
}
}
