Leetcode 128. Longest Consecutive Sequence (union find)
2024-09-08 08:12:36
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is[1, 2, 3, 4]. Therefore its length is 4.
tag : union find
create the array first and then union the consecutive number (3,4) (4,5) -- > have the same root
e.g: 100 4 200 1 3 2
100 4 200 1 3 2
My method: weighted union find with hashmap;
Solution 1
class Solution {
//union find
class QuickUnion {//with array
HashMap<Integer, Integer> map = new HashMap<>(); // id, parent
HashMap<Integer, Integer> sz = new HashMap<>(); // id size
int count;//how many components
QuickUnion(int[] nums){
count = 1;
for(int i = 0; i<nums.length;i++) {
map.put(nums[i],nums[i]);
sz.put(nums[i],1);
}
}
Integer root(int p){
if(!map.containsKey(p)) return null; // there is no such id
while(p != map.get(p)){
int temp = map.get(map.get(p));//with path compression , set parent -> grandparent, map.get(i): i 's parent
map.put(p, temp);
p = map.get(p);
}
/*while(id[p] != p){//find the root when to stop
id[p] = id[id[p]];
p = id[p];
}*/
return p;
}
boolean find(int p, int q){
return root(p)==root(q);
}
void union(int p, int q){
//get root
Integer pid = root(p);
Integer qid = root(q);
System.out.println(qid);
if(pid == null || qid == null) return; // check the null
//if(pid == qid) return; // check the integer,. heck if in the same set
if(pid.equals(qid)) return;
if(sz.get(pid) > sz.get(qid)){
map.put(qid, pid);
sz.put(pid, sz.get(pid)+sz.get(qid));
if(sz.get(pid)>count) count = sz.get(pid);
}else{
map.put(pid, qid);
sz.put(qid, sz.get(pid)+sz.get(qid));
if(sz.get(qid)>count) count = sz.get(qid);
}
}
}
public int longestConsecutive(int[] nums) {
//create a union find
//union the elemnt 4 (3,5) -> 3,4,5
if(nums.length == 0) return 0;
QuickUnion qu = new QuickUnion(nums);
for(int i = 0; i<nums.length; i++){
System.out.println("num of i"+i+" ");
if(nums[i] != Integer.MIN_VALUE) qu.union(nums[i],nums[i]-1);//check the boundary
if(nums[i] != Integer.MAX_VALUE) qu.union(nums[i],nums[i]+1);//[2147483646,-2147483647,0,2,2147483644,-2147483645,2147483645]
System.out.println(qu.count+" ");
}
return qu.count;
}
}
Solution: hashset
remove and contains in ahshset
flow: remove the element : visited that element
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length==0) return 0;
//use hashset
HashSet<Integer> set = new HashSet<>();//non duplicate element
for(int num : nums){
set.add(num);
}
int max = 1;
for(int num : nums){
int len = 0;
int left = 1, right = 1;
if(!set.contains(num)) continue;
while(set.contains(num-left)){
set.remove(num-left); left++; len++;
}
while(set.contains(num+right)){
set.remove(num+right); right++; len++;
}
len++;
set.remove(num);
max = Math.max(len, max);
}
return max;
}
}
quick find and quick union and weightedunion find
public class QuickFind{
private int[] id; // set all root of current id
public QuickFind(int N){
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
//Check if p and q have the same id.
boolean find(int p, int q){
return id[p]==id[q];
}
//union pq
void unite(int p, int q){
int pid = id[p];//change pid to q
for(int i = 0; i <id.length; i++){
if(id[i] == pid) id[i] = id[q];
}
}
}
public class QuickUnion{
private int[] id; //represent the parent instead of root
public QuickUnion(int N){
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
//Check if p and q have the same id.
boolean find(int p, int q){
return root(p)==root(q);
}
//get the root
int root(int i){
while(i != id[i]) i = id[i];//id[i] parent i: children
return i;
}
//union p q
void unite(int p, int q){
//find root first
int i = root(p);
int j = root(q);
id[i] = j;
}
}
//avoid the tall trees , keep track ther size of each component
public class WeightedQuickUnion{
private int[] id; //represent the parent instead of root
private int[] sz;
int count;
public WeightedQuickUnion(int N){
count = N;
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++){
id[i] = i;
sz[i] = 1;
}
}
//Check if p and q have the same id.
boolean find(int p, int q){
return root(p)==root(q);
}
//get the root
int root(int i){
while(i != id[i]) {
// path compression
id[i] = id[id[i]];
i = id[i];//id[i] parent i: children
}
return i;
}
//union p q
void unite(int p, int q){
//find root first
int i = root(p);
int j = root(q);
if(sz[i]<sz[j]){ //samller tree to larger tree
id[i] = j; sz[j]+=sz[i];
}else {
id[j] = i; sz[i]+=sz[j];
}
count--;
}
}
最新文章
- 20145208 《Java程序设计》第0周学习总结
- ajax-向服务器发送请求
- sap 怎么导出sap的各种表
- apiCloud结合layer实现动态数据弹出层
- IOS用CGContextRef画各种图形(文字、圆、直线、弧线、矩形、扇形、椭圆、三角形、圆角矩形、贝塞尔曲线、图片)
- Fedora 15 KDE中如何打开software management及如何应用
- phpstorm集成phpunit（转）
- 第1章 网络编程基础(4)——TCP/IP通信
- java定义和实现接口
- vb代码之-------当窗体BorderStyle属性为0时，添加窗口预览到任务栏
- 使用Maven+Nexus+Jenkins+Svn+Tomcat+Sonar搭建持续集成环境
- springcloud之hystrix熔断器-Finchley.SR2版
- CentOS 安装 ceph 单机版（luminous版本）
- java10.0.2和java 11.0.1配置环境变量
- Firebug: 已拦截跨源请求：同源策略禁止读取位于XXX的远程资源。（原因：CORS 头缺少 'Access-Control-Allow-
- 一张图看懂AI、机器学习和深度学习的区别
- JAVA获取客户端请求的当前网络ip地址（附：Nginx反向代理后获取客户端请求的真实IP）
- C++对象的构造、析构与拷贝构造
- python全栈开发day24-__new__、__del__、item系列、异常处理
- gdb 内存查看