当前位置: 首页 > 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…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...