最主要的思路是将所有数存入set集合,然后再遍历数组,如果一个数不是当前连续序列的第一个,则不计数,当它是序列中第一个数才统计其所在连续序列的长度。
这样做正确是因为如果一个数不是一个连续序列的开头,那么从它开始往后查找总拿不到最长的连续序列的长度,我们贪心的用一个连续序列的开始元素去计算其长度,能够将时间均摊到O(1)O(1)O(1)。
class Solution {
public int longestConsecutive(int[] nums) {
int ans = 0;
Set<Integer> set = new HashSet<>();
for(int num : nums){
set.add(num);
}
for(int num : set){
// 如果set中存在num之前的一个数,说明当前num不是连续序列的开始
if(set.contains(num-1))
continue;
int cur = num;
// 此时num为一个连续序列的开始,现在才统计其所在连续序列长度
// 在整个for循环中,此while循环总共走了n次,因为数组中的数只属于一个连续序列
// 而我们每次只从连续序列的开始往后走
while(set.contains(cur))
cur++;
ans = Math.max(cur-num, ans);
}
return ans;
}
}
map中key是连续序列的端点,value存的是该区间的长度,详见代码
class Solution {
public int longestConsecutive(int[] nums) {
int ans = 0;
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums){
// 如果num不在任何已存在的区间
if(!map.containsKey(num)){
// 当前num不存在于区间,找到以num-1为结尾的连续区间的长度
int lLen = map.getOrDefault(num-1, 0);
// 找到以num+1为开始的连续区间的长度
int rLen = map.getOrDefault(num+1, 0);
// 加入num之后最新的区间长度
int curLen = lLen + rLen + 1;
ans = Math.max(ans, curLen);
// num为区间[num-lLen, num+rLen]中的值,无论存什么值都无所谓
// 因为在找区间的时候只会找到num所在的连续序列的左右端点
map.put(num, -1);
// 更新左端点开始连续序列的长度
map.put(num-lLen, curLen);
// 更新右端点结尾连续序列的长度
map.put(num+rLen, curLen);
}
}
return ans;
}
}
union
起来class Solution {
Map<Integer, Integer> parents = new HashMap<>();
Map<Integer, Integer> count = new HashMap<>();
// 带路径压缩的找上司
public int find(int x){
int p = parents.get(x);
if(p == x)
return p;
// t为x的最终boss
int t = find(p);
// 直接将x的上司设置为t,将路径压缩
parents.put(x, t);
return t;
}
// 将x与y联合
public void union(int x, int y){
int p1 = find(x);
int p2 = find(y);
if(p1 == p2)
return;
// 若x与y的上司不是同一个人,则设置p2为p1的上司
parents.put(p1, p2);
// 此时p2手下的人数就为p1手下管理的人数加p2手下的人数
count.put(p2, count.get(p1) + count.get(p2));
}
public int longestConsecutive(int[] nums) {
int ans = 0;
Set<Integer> set = new HashSet<>();
// set去重,同时初始化parents和count
for(int num : nums){
parents.put(num, num);
count.put(num, 1);
set.add(num);
}
for(int num : set){
if(set.contains(num-1))
union(num, num-1);
if(set.contains(num+1))
union(num, num+1);
// 查找num的最终boss的管理人数与当前ans相比,留最大
ans = Math.max(ans, count.get(find(num)));
}
return ans;
}
}