并查集 size 的优化(并查集 size 的优化)
目录
并查集 size 的优化
Java 实例代码
UnionFind3.java 文件代码:
并查集 size 的优化
按照上一小节的思路,我们把如下图所示的并查集,进行 union(4,9) 操作。

合并操作后的结构为:

可以发现,这个结构的树的层相对较高,若此时元素数量增多,这样产生的消耗就会相对较大。解决这个问题其实很简单,在进行具体指向操作的时候先进行判断,把元素少的集合根节点指向元素多的根节点,能更高概率的生成一个层数比较低的树。
构造并查集的时候需要多一个参数,sz 数组,sz[i] 表示以 i 为根的集合中元素个数。
// 构造函数
public UnionFind3(int count){
parent = new int[count];
sz = new int[count];
this.count = count;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
sz[i] = 1;
}
}
在进行合并操作时候,根据两个元素所在树的元素个数不同判断合并方向。
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
if( sz[pRoot] < sz[qRoot] ){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
优化后,合并结果如下,9 指向父节点 8。

Java 实例代码
源码包下载:Download
UnionFind3.java 文件代码:
package runoob.union;
/**
* 并查集size的优化
*/
public class UnionFind3 {
// parent[i]表示第一个元素所指向的父节点
private int[] parent;
// sz[i]表示以i为根的集合中元素个数
private int[] sz;
// 数据个数
private int count;
// 构造函数
public UnionFind3(int count){
parent = new int[count];
sz = new int[count];
this.count = count;
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
sz[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( sz[pRoot] < sz[qRoot] ){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}
相关文章:
并查集 size 的优化(并查集 size 的优化)
目录 并查集 size 的优化 Java 实例代码 UnionFind3.java 文件代码: 并查集 size 的优化 按照上一小节的思路,我们把如下图所示的并查集,进行 union(4,9) 操作。 合并操作后的结构为: 可以发现,这个结构的树的层相对…...
Qt关于hex转double,或者QByteArray转double
正常的00 ae 02 33这种类型的hex数据类型可以直接通过以下代码进行转换 double QDataConversion::hexToDouble(QByteArray p_buf) {double retValue 0;if(p_buf.size()>4){QString str1 byteArrayToHexStr(p_buf.mid(0,1));QString str2 byteArrayToHexStr(p_buf.mid(1,…...
Java“牵手”根据关键词搜索(分类搜索)拼多多商品列表页面数据获取方法,拼多多API实现批量商品数据抓取示例
拼多多商城是一个网上购物平台,售卖各类商品,包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取拼多多商品列表和商品详情页面数据,您可以通过开放平台的接口或者直接访问拼多多商城的网页来获取商品列表和详情信息。以下是两种常用方…...
Linux相关知识点
Linux是什么? Linux是一套免费使用和自由传播的类Unix操作系统,是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的UNIX工具软件、应用程序和网络协议。它支持32位和64位硬件。 Linux内核 是一个Linux系统的内核&…...
常见的的数据结构
数组(Array):一组按顺序排列的元素的集合,可以通过索引访问和修改元素。 链表(Linked List):由一系列节点组成的数据结构,每个节点包含数据和指向下一个节点的指针。 栈࿰…...
专业心理咨询师助你轻装上阵,向内耗说不!
引言 身为技术人,你是否经常感觉自己被掏空了精力,行动力不佳?又或者觉得自己的工作没有成就和意义,工作状态持续不佳?你是否总有一种无法消除的疲惫?即使没有学习、工作,而是选择看剧、刷短视频…...
Ubuntu安装mysql5.7
目录 1. 更新系统软件包2. 安装MySQL 5.73. 启动MySQL 服务4. 设置MySQL root 密码5. 验证MySQL 安装6. 启用远程访问7. 创建新用户8. 为新用户授予权限9. mysql命令 以Ubuntu 18.04系统为例,安装MySQL 5.7。操作步骤如下: 1. 更新系统软件包 sudo apt…...
vue2,使用element中的Upload 上传文件,自定义上传http-request上传,上传附件支持多选,多个文件只发送一次请求,代码里有注释
复制直接使用,组件根据multiple是否多选来返回附件内容,支持多选就返回数据附件,则返回一个附件对象。 //uploadFiles.vue<template><div><el-uploadclass"avatar-uploader"action"#":accept"accep…...
flutter定位简单工具类
import package:permission_handler/permission_handler.dart;class PermissionUtil {/// 获取用户定位权限static Future<bool> getLocationStatus() async {Map<Permission, PermissionStatus> statuses await [Permission.location,].request();return statuse…...
java请求SAP系统,发起soap的xml报文,实体类转换,idea自动生成教程
1、将接口的网页地址,右键保存,然后修改文件后缀为wsdl文件 2、idea全局搜索 wsdl,找到自动转换javabean插件: 3、点击后,选择下载改完后缀的文件(选择): 4、将无用的class文件删除掉 5、请求sap的地址为…...
不同屏幕的触控技术
不同显示屏的触控技术原理有所不同。触摸屏的基本原理是,用手指或其他物体触摸安装在显示器前端的触摸屏时,所触摸的位置(以坐标形式)由触摸屏控制器检测,并通过接口(如RS-232串行口)送到CPU,从而确定输入的信息。 目前市场上常…...
深度解读thenable
在学习promise时,我们经常会遇到thenable一词。关于thenable,目前的资料解读不够通俗易懂,又或者脉络不够清晰,本文主要对thenable进行详细剖析,以便各位参考。笔者希望你能够仅凭这一篇文章,便能深度掌握该…...
原生无限极目录树详细讲解
原生无限级目录树 当涉及到原生的无限级目录树,我们可以使用递归算法来实现。以下是一个使用 JavaScript 实现原生无限级目录树的示例 介绍 原生无限级目录树是一种常见的数据结构,用于组织多层级的目录或分类数据。通过递归算法,我们可以…...
剑指offer(C++)-JZ64:求1+2+3+...+n(算法-位运算)
作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 求123...n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句&…...
“深入探究JVM内部机制:如何实现Java程序的运行环境?“
标题:深入探究JVM内部机制:如何实现Java程序的运行环境? 摘要:本文将深入探究Java虚拟机(JVM)的内部机制,重点讨论JVM如何实现Java程序的运行环境。我们将从JVM的结构、类加载、内存管理、垃圾…...
Mac更新homebrew时卡住的解决办法
Mac更新homebrew时卡住的解决办法 引起问题的原因brew命令安装软件跟这3个仓库地址有关1、brew2、homebrew-core3、homebrew-bottles4、若/bin/zsh,则输入5、若/bin/bash,则输入6、更新brew 引起问题的原因 知其然,还要知其所以然。brew的更…...
带你了解—在外远程群晖NAS-群晖Drive挂载电脑磁盘同步备份【无需公网IP】
文章目录 前言1.群晖Synology Drive套件的安装1.1 安装Synology Drive套件1.2 设置Synology Drive套件1.3 局域网内电脑测试和使用 2.使用cpolar远程访问内网Synology Drive2.1 Cpolar云端设置2.2 Cpolar本地设置2.3 测试和使用 3. 结语 前言 群晖作为专业的数据存储中心&…...
计算机网络第2章(物理层)
计算机网络第2章(物理层) 2.1 物理层的基本概念2.2 物理层下面的传输媒体2.2.1 导引型传输媒体2.2.2 非导引型传输媒体 2.3 传输方式2.3.1 串行传输和并行传输2.3.2 同步传输和异步传输2.3.3 单向通信(单工)、双向交替通信&#x…...
windows钩子保护自身进程不被破坏
代码来自于《windows核心编程》作者: APIHOOK.h头文件: #pragma once #include <Windows.h> class CAPIHOOK { public: CAPIHOOK(LPTSTR lpszModName, LPSTR pszFuncName, PROC pfnHook, BOOL bExcludeAPIHookMod TRUE); ~CAPIHOOK(void); p…...
Linux系统查看文件系统类型C代码
系统:VM Ubuntu 实现Linux系统下通过输入指定路径查看文件系统类型,MSDOS_SUPER_MAGIC,NTFS_SUPER_MAGIC和EXT4_SUPER_MAGIC这些宏定义并不是在sys/mount.h中定义的,它们实际上是在linux/magic.h头文件中定义的。不同系统下宏定义可能不一样&…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
