当前位置: 首页 > news >正文

并查集 rank 的优化(Java 实例代码)

目录

 

并查集 rank 的优化

Java 实例代码

UnionFind3.java 文件代码:


 

并查集 rank 的优化

上一小节介绍了并查集基于 size 的优化,但是某些场景下,也会存在某些问题,如下图所示,操作 union(4,2)。

 

7561a182ed69e7dafb5bef57311d44d5.png

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

 

3fb31fb1d2b9eac6cddd03a4181a5e66.png

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

 

56512f102f1baf3bf7b91a8c2c34d19b.png

我们在并查集的属性中,添加 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 文件代码&#xff1a; 并查集 rank 的优化 上一小节介绍了并查集基于 size 的优化&#xff0c;但是某些场景下&#xff0c;也会存在某些问题&#xff0c;如下图所示&#xff0c;操作 union(4,2)。 根据上一小节&…...

TDA4超级玩家浮出水面,行泊一体功能、成本刷到极致

2023年以来&#xff0c;智能驾驶市场进入L2普及、高阶ADAS功能&#xff08;NOA&#xff09;大规模量产的新周期&#xff0c;降本增效&#xff0c;打造极致性价比、提升用户体验等&#xff0c;成为了竞争的焦点。 其中&#xff0c;替换更具性价比的硬件平台、传感器复用、系统优…...

3分钟了解Android中稳定性测试

一、什么是Monkey Monkey在英文里的含义是猴子&#xff0c;在测试行业的学名叫“猴子测试”&#xff0c;指的是没有测试经验的人甚至是根本不懂计算机的人&#xff08;就像一只猴子&#xff09;&#xff0c;不需要知道程序的任何用户交互方面的知识&#xff0c;给他一个程序&a…...

LVS-DR+keepalived实现高可用负载群集

VRRP 通信原理&#xff1a; VRRP就是虚拟路由冗余协议&#xff0c;它的出现就是为了解决静态路由的单点故障。 VRRP是通过一种竞选的一种协议机制&#xff0c;来将路由交给某台VRRP路由。 VRRP用IP多播的方式&#xff08;多播地址224.0.0.18&#xff09;来实现高可用的通信&…...

阿里云国际版注册教程

什么是阿里云国际版&#xff1f; 阿里云国际版是阿里云专为海外客户供给的服务器及核算资源&#xff0c;涵盖了云主机、弹性裸金属服务器、容器服务、数据库及安全和监控等一系列云核算解决方案。 与其他云核算服务供给商不同&#xff0c;阿里云国际版在安全性、稳定性、性能方…...

基于百度文心大模型创作的实践与谈论

文心概念 百度文心大模型源于产业、服务于产业&#xff0c;是产业级知识增强大模型。百度通过大模型与国产深度学习框架融合发展&#xff0c;打造了自主创新的AI底座&#xff0c;大幅降低了AI开发和应用的门槛&#xff0c;满足真实场景中的应用需求&#xff0c;真正发挥大模型…...

Java基础知识题(五)

系列文章目录 Java基础知识题(一) Java基础知识题(二) Java基础知识题(三) Java基础知识题(四) Java基础知识题(五) 文章目录 系列文章目录 前言 一 Java的数据连接——JDBC 1. 简述什么是JDBC&#xff1f;重点 2. JDBC PreparedStatement比Statement有什么优势&…...

攻防世界-fileinclude

原题 解题思路 题目已经告诉了&#xff0c;flag在flag.php中&#xff0c;先查看网页源代码&#xff08;快捷键CTRLU&#xff09;。 通过抓包修改&#xff0c;可以把lan变量赋值flag。在cookie处修改。新打开的网页没有cookie&#xff0c;直接添加“Cookie: languagephp://filte…...

流媒体服务器SRS的搭建及QT下RTMP推流客户端的编写

一、前言 目前市面上有很多开源的流媒体服务器解决方案&#xff0c;常见的有SRS、EasyDarwin、ZLMediaKit和Monibuca。这几种的对比如下&#xff1a; &#xff08;本图来源&#xff1a;https://www.ngui.cc/zz/1781086.html?actiononClick&#xff09; 二、SRS的介绍 SRS&am…...

Effective C++条款11——在operator=中处理“自我赋值”(构造/析构/赋值运算)

“自我赋值”发生在对象被赋值给自己时: class Widget {}; Widget w; // ... w w; // 赋值给自己 这看起来有点愚蠢&#xff0c;但它合法&#xff0c;所以不要认定客户绝不会那么做。此外赋值动作并不总是那么可被一眼辨识出来&#xff0c;例如: a[i] a[j]; …...

可视化绘图技巧100篇基础篇(八)-气泡图(一)

目录 前言 适用场景 图例 绘图工具及代码实现 EXCEL 1、单轴气泡图...

Elasticsearch查询之Disjunction Max Query

前言 Disjunction Max Query 又称最佳 best_fields 匹配策略&#xff0c;用来优化当查询关键词出现在多个字段中&#xff0c;以单个字段的最大评分作为文档的最终评分&#xff0c;从而使得匹配结果更加合理 写入数据 如下的两条例子数据&#xff1a; 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安装数据库是一个非常好的选择&#xff0c;后续的读写分离、数据分片等功能的数据库都是由docker创建。 一、安装准备 1、前提条件 Docker可以运行在Windows、Mac、CentOS、Ubuntu等操作系统上 Docker支持以下的CentOS版本&#xff1a; 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 …...

电商系统架构设计系列(九):如何规划和设计分库分表?

上篇文章中&#xff0c;我给你留了一个思考题&#xff1a;分库分表该如何设计&#xff1f; 今天这篇文章&#xff0c;我们来聊一下如何规划和设计分库分表&#xff0c;以及要考虑哪些问题。 引言 当要解决海量数据的问题&#xff0c;就必须要用到分布式的存储集群了&#xff…...

从Web 2.0到Web 3.0,互联网有哪些变革?

文章目录 Web 2.0时代&#xff1a;用户参与和社交互动Web 3.0时代&#xff1a;语义化和智能化影响和展望 &#x1f389;欢迎来到Java学习路线专栏~从Web 2.0到Web 3.0&#xff0c;互联网有哪些变革&#xff1f; ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&#x…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...