并查集 rank 的优化(Java 实例代码)
目录
并查集 rank 的优化
Java 实例代码
UnionFind3.java 文件代码:
并查集 rank 的优化
上一小节介绍了并查集基于 size 的优化,但是某些场景下,也会存在某些问题,如下图所示,操作 union(4,2)。

根据上一小节,size 的优化,元素少的集合根节点指向元素多的根节点。操作完后,层数变为4,比之前增多了一层,如下图所示:

由此可知,依靠集合的 size 判断指向并不是完全正确的,更准确的是,根据两个集合层数,具体判断根节点的指向,层数少的集合根节点指向层数多的集合根节点,如下图所示,这就是基于 rank 的优化。

我们在并查集的属性中,添加 rank 数组,rank[i] 表示以 i 为根的集合所表示的树的层数。
...
private int[] rank; // rank[i]表示以i为根的集合所表示的树的层数
private int[] parent; // parent[i]表示第i个元素所指向的父节点
private int count; // 数据个数
...
构造函数相应作出修改:
...
// 构造函数
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
...
合并两元素的时候,需要比较根节点集合的层数,整个过程是 O(h)复杂度,h为树的高度。
...
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
}
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 此时, 我维护rank的值
}
}
...
Java 实例代码
源码包下载:Download
UnionFind3.java 文件代码:
package runoob.union;
/**
* 基于rank的优化
*/
public class UnionFind4 {
private int[] rank; // rank[i]表示以i为根的集合所表示的树的层数
private int[] parent; // parent[i]表示第i个元素所指向的父节点
private int count; // 数据个数
// 构造函数
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
private int find(int p){
assert( p >= 0 && p < count );
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
}
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 维护rank的值
}
}
}
相关文章:
并查集 rank 的优化(Java 实例代码)
目录 并查集 rank 的优化 Java 实例代码 UnionFind3.java 文件代码: 并查集 rank 的优化 上一小节介绍了并查集基于 size 的优化,但是某些场景下,也会存在某些问题,如下图所示,操作 union(4,2)。 根据上一小节&…...
TDA4超级玩家浮出水面,行泊一体功能、成本刷到极致
2023年以来,智能驾驶市场进入L2普及、高阶ADAS功能(NOA)大规模量产的新周期,降本增效,打造极致性价比、提升用户体验等,成为了竞争的焦点。 其中,替换更具性价比的硬件平台、传感器复用、系统优…...
3分钟了解Android中稳定性测试
一、什么是Monkey Monkey在英文里的含义是猴子,在测试行业的学名叫“猴子测试”,指的是没有测试经验的人甚至是根本不懂计算机的人(就像一只猴子),不需要知道程序的任何用户交互方面的知识,给他一个程序&a…...
LVS-DR+keepalived实现高可用负载群集
VRRP 通信原理: VRRP就是虚拟路由冗余协议,它的出现就是为了解决静态路由的单点故障。 VRRP是通过一种竞选的一种协议机制,来将路由交给某台VRRP路由。 VRRP用IP多播的方式(多播地址224.0.0.18)来实现高可用的通信&…...
阿里云国际版注册教程
什么是阿里云国际版? 阿里云国际版是阿里云专为海外客户供给的服务器及核算资源,涵盖了云主机、弹性裸金属服务器、容器服务、数据库及安全和监控等一系列云核算解决方案。 与其他云核算服务供给商不同,阿里云国际版在安全性、稳定性、性能方…...
基于百度文心大模型创作的实践与谈论
文心概念 百度文心大模型源于产业、服务于产业,是产业级知识增强大模型。百度通过大模型与国产深度学习框架融合发展,打造了自主创新的AI底座,大幅降低了AI开发和应用的门槛,满足真实场景中的应用需求,真正发挥大模型…...
Java基础知识题(五)
系列文章目录 Java基础知识题(一) Java基础知识题(二) Java基础知识题(三) Java基础知识题(四) Java基础知识题(五) 文章目录 系列文章目录 前言 一 Java的数据连接——JDBC 1. 简述什么是JDBC?重点 2. JDBC PreparedStatement比Statement有什么优势&…...
攻防世界-fileinclude
原题 解题思路 题目已经告诉了,flag在flag.php中,先查看网页源代码(快捷键CTRLU)。 通过抓包修改,可以把lan变量赋值flag。在cookie处修改。新打开的网页没有cookie,直接添加“Cookie: languagephp://filte…...
流媒体服务器SRS的搭建及QT下RTMP推流客户端的编写
一、前言 目前市面上有很多开源的流媒体服务器解决方案,常见的有SRS、EasyDarwin、ZLMediaKit和Monibuca。这几种的对比如下: (本图来源:https://www.ngui.cc/zz/1781086.html?actiononClick) 二、SRS的介绍 SRS&am…...
Effective C++条款11——在operator=中处理“自我赋值”(构造/析构/赋值运算)
“自我赋值”发生在对象被赋值给自己时: class Widget {}; Widget w; // ... w w; // 赋值给自己 这看起来有点愚蠢,但它合法,所以不要认定客户绝不会那么做。此外赋值动作并不总是那么可被一眼辨识出来,例如: a[i] a[j]; …...
可视化绘图技巧100篇基础篇(八)-气泡图(一)
目录 前言 适用场景 图例 绘图工具及代码实现 EXCEL 1、单轴气泡图...
Elasticsearch查询之Disjunction Max Query
前言 Disjunction Max Query 又称最佳 best_fields 匹配策略,用来优化当查询关键词出现在多个字段中,以单个字段的最大评分作为文档的最终评分,从而使得匹配结果更加合理 写入数据 如下的两条例子数据: docId: 1 title: java …...
Lock wait timeout exceeded; try restarting transaction的错误
文章目录 一、异常发现二、异常定位1、锁表语句确认2、实际场景排查三、解决思路1、本次解决方式2、其他场景解决思路扩展1、【治标方法】innodb_lock_wait_timeout 锁定等待时间改大2、【治标方法】事务信息查询3、【治标方法】如果杀掉线程依然不能解决,可以查找执行线程耗时…...
ShardingSphere01-docker环境安装
使用docker安装数据库是一个非常好的选择,后续的读写分离、数据分片等功能的数据库都是由docker创建。 一、安装准备 1、前提条件 Docker可以运行在Windows、Mac、CentOS、Ubuntu等操作系统上 Docker支持以下的CentOS版本: CentOS 7 (64-bit)CentOS …...
Java代码审计13之URLDNS链
文章目录 1、简介urldns链2、hashmap与url类的分析2.1、Hashmap类readObject方法的跟进2.2、URL类hashcode方法的跟进2.3、InetAddress类的getByName方法 3、整个链路的分析3.1、整理上述的思路3.2、一些疑问的测试3.3、hashmap的put方法分析3.4、反射3.5、整个代码 4、补充说明…...
区间预测 | MATLAB实现QRBiGRU双向门控循环单元分位数回归时间序列区间预测
区间预测 | MATLAB实现QRBiGRU双向门控循环单元分位数回归时间序列区间预测 目录 区间预测 | MATLAB实现QRBiGRU双向门控循环单元分位数回归时间序列区间预测效果一览基本介绍模型描述程序设计参考资料 效果一览 基本介绍 MATLAB实现QRBiGRU双向门控循环单元分位数回归时间序列…...
Python面向对象植物大战僵尸
先来一波效果图 来看看如何设计游戏架构 import sysimport pygameclass BaseSprite(pygame.sprite.Sprite):def __init__(self, name):super().__init__()self.image pygame.image.load(name)self.rect self.image.get_rect()class AnimateSprite(BaseSprite):def __init__(…...
大屏模板,增加自适应(包含websocket)
1、简单的Node服务端 const WebSocket require(ws);// 创建 WebSocket 服务器 const wss new WebSocket.Server({ port: 8888 });const getHeader (protocol) > {const protocolArr protocol.split(,)const headers {};for (let i 0; i < protocolArr.length; i …...
电商系统架构设计系列(九):如何规划和设计分库分表?
上篇文章中,我给你留了一个思考题:分库分表该如何设计? 今天这篇文章,我们来聊一下如何规划和设计分库分表,以及要考虑哪些问题。 引言 当要解决海量数据的问题,就必须要用到分布式的存储集群了ÿ…...
从Web 2.0到Web 3.0,互联网有哪些变革?
文章目录 Web 2.0时代:用户参与和社交互动Web 3.0时代:语义化和智能化影响和展望 🎉欢迎来到Java学习路线专栏~从Web 2.0到Web 3.0,互联网有哪些变革? ☆* o(≧▽≦)o *☆嗨~我是IT陈寒🍹✨博客主页&#x…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
