AlgoPressAppearance
0128-最长连续序列
https://leetcode.cn/problems/longest-consecutive-sequence
给定一个未排序的整数数组 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
思路 【官方】
- 暴力思路，选定一个数，nums[i] 依次递增，看数组中是否存在nums[i]+，是的话就加+1，直到停止。 这个方法会循环两层，复杂度 O(n^2)
- 将所有数字去重加入Hash表，从 nums[i] 递增，如果发现 Hash 表中存在 key 则继续，直到停止。
- 将第二步优化，比如 数组中有 3 和 2 ，那么从3开始计数得出的结果，一定比从2计数得出的结果+1，所以没有必要计算3，直接找没有前驱的节点开始计算 因为省略了所有带有前驱节点的计算，所以总体复杂度是 O(n)
参考代码
csharp
public class Solution {
public int LongestConsecutive(int[] nums) {
HashSet<int> set = new HashSet<int>();
for(int i=0; i<nums.Length; i++){
if(!set.Contains(nums[i])){
set.Add(nums[i]);
}
}
int maxStrike = 0;
int curStrike = 0;
foreach(int key in set){
int preKey = key - 1;
if(!set.Contains(preKey)){
curStrike = 1;
int nextKey = key+1;
while(set.Contains(nextKey)){
curStrike++;
nextKey++;
}
maxStrike = Math.Max(maxStrike,curStrike);
}
}
return maxStrike;
}
}
复习:20220520
题目要求 O(n) 时间复杂度， 所以我们需要借助空间。 使用哈希表记录每个数字是否出现过。 考虑记录最小数字 min 和 最大数字 max ，然后根据哈希表的key统计连击，后来发现这样效率很低，会超时。 比如 [1,2,99999999] 这样的数组. 考虑根据哈希表的key，然后检查 key+1 是否存在，是则连击，否则 strike = 0; 再考虑到，比如已经有连续的数 2,3,4 存在，所以从4和3统计就没有意义，因为统计2的时候+1，肯定会统计到3和4，所以我们要找到没有前驱节点的开始统计才有意义，即 prekey = key-1不存在的.
csharp
public class Solution {
public int LongestConsecutive(int[] nums) {
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int i=0; i<nums.Length; i++){
if(!dict.ContainsKey(nums[i])){
dict.Add(nums[i],1);
}
}
int maxStrike = 0;
//循环key开始统计
foreach(int key in dict.Keys){
int preKey = key - 1;
if(!dict.ContainsKey(preKey)){
int count = 0;
int strike = 1;
int nextKey = key + 1;
while(dict.ContainsKey(nextKey)){
strike++;
nextKey++;
}
maxStrike = Math.Max(maxStrike,strike);
}
}
return maxStrike;
}
}
并查集：20220703
csharp
public class Solution {
public class UF{
private int[] parent;
private int[] size;
public UF(int n){
parent = new int[n];
size = new int[n];
for(int i=0; i<n; i++){
parent[i] = i;
size[i] = 1;
}
}
public void union(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return;
}
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
public int find(int x){
//路径压缩
if(parent[x] != x){
parent[x] = find(parent[x]);
}
return parent[x];
}
public int getMaxConnectSize(){
int maxSize = 0;
for(int i=0; i<parent.Length; i++){
if(i == parent[i]){
maxSize = Math.Max(maxSize, size[i]);
}
}
return maxSize;
}
}
public int LongestConsecutive(int[] nums) {
int n = nums.Length;
UF uf = new UF(n);
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int i=0; i<n; i++){
if(dict.ContainsKey(nums[i])){
continue;
}
if(dict.ContainsKey(nums[i] - 1)){ //查看是否前一个存在，是的话就连接
uf.union(i, dict[nums[i]-1]);
}
if(dict.ContainsKey(nums[i] + 1)){ //查看是否后一个存在，是的话就连接
uf.union(i, dict[nums[i]+1]);
}
dict.Add(nums[i],i);
}
return uf.getMaxConnectSize();
}
}