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

并查集——从LeetCode题海中总结常见套路

目录

并查集定义

LeetCode128.最长连续序列

先去重再sort:

改进去重的方法:

参考:


并查集定义

在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(Union-find Algorithm)定义了两个用于此数据结构的操作:

    Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
    Union:将两个子集合并成同一个集合。
    由于支持这两种操作,一个不相交集也常被称为联合-查找数据结构(Union-find Data Structure)或合并-查找集合(Merge-find Set)。

为了更加精确的定义这些方法,需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素,称为代表,以表示整个集合。接着,Find(x)Find(x)Find(x) 返回 xxx 所属集合的代表,而 Union 使用两个集合的代表作为参数。

LeetCode128.最长连续序列

先去重再sort:

不满足O(N)复杂度的要求,但是却可以击败99%,离谱……

class Solution {
public:int longestConsecutive(vector<int>& nums) {if (nums.empty())return 0;int ans = 1, len = 0;// 去重unordered_set<int> s(nums.begin(), nums.end());vector<int> v(s.begin(), s.end());sort(v.begin(), v.end());for (int i = 1; i < v.size(); i++) {if (v[i] == v[i - 1] + 1) {len++;} else {if (len == 0) {continue;} else {ans = max(ans, len + 1);len = 0;}}}// 进行到最后一个字符的时会出现统计疏漏,需要特别判断一下if (len != 0) {ans = max(ans, len + 1);len = 0;}return ans;}
};

改进去重的方法:

很快提高了空间复杂度!理论上时间复杂度是有提高的,但是LeetCode大数测试点肯定是有问题的……

class Solution {
public:int longestConsecutive(vector<int>& nums) {if (nums.empty())return 0;int ans = 1, len = 0;sort(nums.begin(), nums.end());for (int i = 1; i < nums.size(); i++) {if (nums[i] == nums[i - 1]) // 改进去重的过程continue;if (nums[i] == nums[i - 1] + 1) {len++;} else {if (len == 0) {continue;} else {ans = max(ans, len + 1);len = 0;}}}// 进行到最后一个字符的时会出现统计疏漏,需要特别判断一下if (len != 0) {ans = max(ans, len + 1);len = 0;}return ans;}
};

参考:

  • 力扣

http://www.lryc.cn/news/454215.html

相关文章:

  • 深入理解作用域【JavaScript】
  • 微信小程序实战教程:如何使用map组件实现地图功能
  • 张雪峰谈人工智能技术应用专业的就业前景!
  • 机器学习课程学习周报十五
  • rabbitMq------客户端模块
  • 地理定位营销与开源AI智能名片O2O商城小程序的融合与发展
  • 解决Vue应用中遇到路由刷新后出现 404 错误
  • 在window10下使用directml加速phi-3模型的一些记录
  • 通信工程学习:什么是OSPF开放式最短路径优先
  • 《中国电子报》报道: 安宝特AR为产线作业者的“秘密武器
  • 【Android】Handler消息机制
  • 大数据必懂知识点:Parquet、ORC还是Avro作为数据存储格式,哪种在性能和压缩率上更优
  • P1387 最大正方形
  • Python知识点:如何使用Multiprocessing进行并行任务管理
  • React常见优化问题
  • css 简单网页布局——浮动(一)
  • 设计模式(3)builder
  • Day01-MySQL数据库介绍及部署
  • 分享一个餐饮连锁店点餐系统 餐馆食材采购系统Java、python、php三个版本(源码、调试、LW、开题、PPT)
  • 解决跨域问题
  • 面试知识储备-多线程
  • 边缘计算插上AI的翅膀会咋样?
  • 脉冲神经网络(SNN)论文阅读(六)-----ECCV-2024 脉冲驱动的SNN目标检测框架:SpikeYOLO
  • 周报_2024/10/6
  • [深度学习][python]yolov11+bytetrack+pyqt5实现目标追踪
  • 如何使用ssm实现基于Web的穿戴搭配系统的设计与实现+vue
  • JavaScript的设计模式
  • CIKM 2024 | 时空数据(Spatial-temporal)论文总结
  • 计算机毕业设计 网上体育商城系统的设计与实现 Java实战项目 附源码+文档+视频讲解
  • 【数据结构】什么是哈希表(散列表)?