题目链接
思路
- 同样的可以转化为并查集来做,可以把相邻的数字放到一个子集中,每当搜索到一个数字时就判断和他相邻的数字是否在集合中,如果在就合并,为了方便记录每个集合的大小,可以用一个count集合记录每个子集的大小,在合并集合的时候也要更新count数组。
- 这个题需要注意的就是并查集的另一种使用方式:
- 首先把所有数字放入allNum中,同时初始化fathers集合和count集合
- 然后遍历每一个allNum中的数字,对于每个数字都判断一下相邻的数字是否在集合中,如果在的话就进行合并处理
- 最后找出最大集合元素数目即可
class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer,Integer> fathers = new HashMap<>();
Map<Integer,Integer> count = new HashMap<>();
Set<Integer> allNum = new HashSet<>();
for(int num : nums){
fathers.put(num,num);
count.put(num,1);
allNum.add(num);
}
for(int num : allNum){
if(allNum.contains(num-1))
union(fathers,count,num,num-1);
if(allNum.contains(num+1))
union(fathers,count,num,num+1);
}
int result = 0;
for(int key : count.keySet()){
result = Math.max(result,count.get(key));
}
return result;
}
private int findFather(Map<Integer,Integer> fathers , int key){
int father = fathers.get(key);
if(father != key)
fathers.put(key,findFather(fathers,father));
return fathers.get(key);
}
private void union(Map<Integer,Integer> fathers , Map<Integer,Integer> count ,int i , int j){
int fatherOfI = findFather(fathers,i) , fatherOfJ = findFather(fathers,j);
if(fatherOfI != fatherOfJ){
fathers.put(fatherOfI,fatherOfJ);
count.put(fatherOfJ,count.get(fatherOfJ) + count.get(fatherOfI));
count.remove(fatherOfI);
}
}
}